[Python/파이썬] 백준 알고리즘 11052번 - 카드 구매하기 (DP)

 

 

 

<풀이>

지금까지 푼 문제 중에는 가장 까다로웠다..

다이나믹 프로그래밍을 통해 푸는 문제다.

 

먼저 Bottom-Up 방식으로 dp의 1번 인덱스부터 차근차근 생각해보겠다.

편의상 Pi 카드팩을 i번 카드팩이라고 부르겠다.

 

dp[1] = 1을 만드는 방법 : 1번 카드팩 1개

dp[2] = 2를 만드는 방법 : 2번 카드팩 1개 or 1번 카드팩 2개 중 큰 것

dp[3] = 3을 만드는 방법 : 3번 카드팩 1개 or 1번 카드팩 1개 + dp[2] 중 큰 것

(여기서 1,1,1로 3을 만드는 경우, 1,2로 3을 만드는 경우는 dp[2]에서 처리가 끝난 것이다.)

...

dp[n] = n을 만드는 방법 : n번 카드팩 1개 or 1번 카드팩 1개 + dp[n-1] or dp[2] + dp[n-2] or .. dp[i] + dp[n-i] 중 큰 수이다.

N = int(input())
# 편의상 cost 리스트의 0번 인덱스는 사용 x
cost = [0]
cost += list(map(int, input().split()))

dp = [0] * (N+1)
dp[1] = cost[1]
dp[2] = max(cost[2], cost[1]*2)

for i in range(3, N+1):
    dp[i] = cost[i]     # i개 들어있는 카드팩을 하나 사는 경우
    for j in range(1, i//2 + 1):    # j와 i-j로 만드는 경우
        dp[i] = max(dp[i], dp[j] + dp[i-j])

print(dp[N])

 

 

 

<핵심 정리>

1. 까다로운 DP 문제를 만날때는 Bottom-Up 방식으로 직접 수열을 나열해보자.