백준 11052 카드 구매하기

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

11052번: 카드 구매하기

 

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

for i in range(2,n+1):
    for j in range(1,i+1):
        if dp[i] < dp[i-j] + data[j]:
            dp[i] = dp[i - j] + data[j]

print(dp[n])

DP, 다이나믹 프로그래밍 문제 이기 때문에  리스트를 먼저 선언한다.

편리함을 위해 index 0은 0으로 초기화 하고 시작하자.

dp[1]은 data[1]와 동일하다. why) 카드 1개를 뽑는 최댓값은 1개의 값이기 때문!

 

카드를 3개 이상사는것부터 최댓값을 구하려면 모든 경우를 고려해야하지만 최댓값을 구하는것이기 때문에

n개를 산다하면 

 

dp[2] = dp[1] + data[1]  # 1장 + 1장

           dp[0] + data[2]  # 2장짜리 1개 사는 경우

 

dp[3] = dp[2] + data[1]  # 2장 최댓값 + 1장

           dp[1] + data[2]  #1장 최댓값 + 2장

           dp[0] + data[3]  #3장짜리 1개 사는 경우

 

dp[4] = dp[3] + data[1] # 3장 최댓값 + 1장

           dp[2] + data[2] # 2장 최댓값  + 2장 

           dp[1] +data[3]  # 1장 최댓값 + 3장

           dp[0] + data[4] # 4장짜리 1개 사는 경우

 

 

이렇게 순서쌍을 두고 최댓값을 찾는식으로 풀면 해결 가능