백준 11052번 파이썬 문제풀이(DP - 카드 구매하기)

---

N = int(input())

P = [0] + list(map(int, input().split()))
dp = [0] * (N + 1)

dp[1] = P[1]

for i in range(1, N + 1):
    for j in range(1, i + 1):
        if dp[i] < dp[i - j] + P[j]:
             dp[i] = dp[i-j] + P[j]
        #dp[i] = max(dp[i], dp[i - j] + P[j]) 위의 if문을 다음과 같이 한줄로도 가능 단, 시간복잡도 보장x
			
print(dp[N])

-> 이 문제가 왜 DP로 풀 수 있냐면 1개부터 N개까지 개수마다 최대비용을 저장하고 그 다음 비용을 구할때 저장한 값을 가지고 활용을 할 수 있다는 것이다.

 

무슨말이나면 예를들어 1개를 살때의 최대값이 dp[1]에 2개를 살때의 최대값이 dp[2]에 저장이 되어 있다고 하자. 그럼 3개를 구매할때는 1개를 살때의 최대값에다가 2팩짜리 1개를 구매하거나 2개를살때의 최대값에다가 1팩짜리 1개를 구매하면 된다. 혹은 그냥 3팩짜리 1개를 구매할 수도 있다. 이 3개의 값을 비교해서 큰 값을 dp[3] 에다가 저장하는 것이다.

 

식을 정리하자면 다음과 같이 표현할 수 있다.

dp[2] = dp[1] + p[1] or dp[0] + p[2]

dp[3] = dp[2] + p[1] or dp[1] + p[2] or dp[0] + p[3]

dp[4] = dp[3] + p[1] or dp[2] + p[2] or dp[1] + p[3] or dp[0] + p[4]

 

처음에 생각하기 쉽지 않은 문제였다. 정답률 꽤 높은것을 보고 놀랐는데 알고나니 쉬운 DP였다.