[백준] 11052.카드 구매하기(python, 파이썬)

문제

11052.카드 구매하기

📌 아이디어

이 문제를 풀기 위해 처음 떠올렸던 접근 방법은 DFS였습니다. 완전 탐색을 진행하며 카드의 개수가 N이 된다면 최댓값을 갱신하려했습니다. 하지만 시간초과가 발생하였고, 이를 해결하기 위해 DP를 사용했습니다. 1 ~ N까지 탐색하며 해당 인덱스에서 조합할 수 있는 최대값을 갱신해 나간다며 최종적으로 DP[N]에서는 문제의 답을 도출 할 수 있습니다.

1. 먼저 최댓값을 갱신하기 위한 DP 테이블을 만듭니다.
2. 1 ~ N까지 탐색하며 해당 인덱스에서의 최대값을 갱신합니다.
3. 최종적으로 DP[N]에서의 최댓값을 도출합니다.

📌 코드

N = int(input())
cost = [0]
tmp = list(map(int, input().split()))
cost.extend(tmp)

dp = [0] * (N+1)
# 1 ~ N까지 탐색하며 최대값 갱신
for i in range(1, N+1):
	# 인덱스 조절을 통해 현재 인덱스의 최대값 갱신
    # 이미 저장된 dp[i]와 현재 인덱스의 비용과 조절한 인덱스의 dp[i-j]합을 비교
    for j in range(1, i+1):
        dp[i] = max(dp[i], cost[j]+dp[i-j])
print(max(dp))

피드백 및 개선점은 댓글을 통해 알려주세요😊