#228 백준 파이썬 [11052] 카드 구매하기

https://www.acmicpc.net/problem/11052

 

Solution

다이나믹 프로그래밍을 통해 풀이할 수 있다.

N의 수를 채우는 방법을 1부터 풀이한다.

다음과 같은 알고리즘을 거친다.

 

dp[1] = 1을 만드는 방법은 1번 카드 1개를 쓰는 방법뿐이다.

dp[2] = 2를 만드는 방법은 2번 카드 1개, 혹은 1번 카드 2개를 쓰는 것 중 큰 수 이다.

dp[3] = 3을 만드는 방법은 3번 카드 1개, 혹은 1과 dp[2]를 쓰는 것 중 큰 수이다. 여기서 1,1,1로 3을 만드는 경우, 1,2로 3을 만드는 경우는 dp[2]에서 처리가 끝난 것이다.

...

dp[n] = n을 만드는 방법은 n번 카드 1개, 혹은 1과 dp[n-1], 혹은 dp[2]와 dp[n-2], ..dp[i]와 dp[n-i]를 만드는 것 중 중 큰 수이다.

 

Python Code

N = int(input())
card = [0]
card += list(map(int, input().split()))

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

for i in range(3, N+1):
    dp[i] = card[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])