[Python] 백준 11052번: 카드 구매하기 풀이

 

소스코드

n = int(input())
p = list(map(int, input().split()))
p.insert(0,0)
dp = [0 for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1,i+1):
        dp[i] = max(dp[i], p[j] + dp[i-j])
print(dp[n])

 

문제가 길어서 지레 겁먹었지만, 사실상 그리 어렵지 않은 문제이다.

 

여느 dp문제처럼 작은 문제 부터 풀어나가면 된다.

즉 1부터 n까지 각각의 카드수를 위한 금액의 최댓값을 구해나가는 것이다.

 

4

3 5 15 16 을 예시로 들자.

dp[1] 은 언제나 p[1] 과 동일할 것이므로 3 일 것이다.

dp[2] 는 dp[1] + p[1] 또는 p[2] 둘 중 큰 값일 것이므로 8 이다.

dp[3] 은 dp[1] + p[2] , dp[2] + p[1] , p[3] 중 큰 값일 것이므로 15가 된다.

마지막으로 dp[4] 는 dp[1] + p[3] , dp[2] + p[2] , dp[3] + p[1] , p[4] 중 큰 값이므로 18 이 된다.

 

즉 점화식으로 표현한다면, 

dp[i] 에 대해서 j는 1부터 i까지 증가하면서, dp[i] = dp[i-j] + p[j] (j값에 따른 max값) 이다.

 

* 인덱스를 0부터 하면 헷갈리는 감이 있어서 임의로 dp[0] 은 0 으로 채우고 1부터 시작했다.