백준 11052 카드 구매하기 / python

문제 : 11052

풀이 point

dp[i]의 경우 i개의 카드를 살때 가장 최댓값이다.

dp[N]을 구하기 위해서는 dp[N-1] + dp[1] or dp[N-2] + dp[2] or dp[N-3] + dp[3] .... 다양한 경우의 수가 있기 때문에 이 경우의 수를 모두 고려하여 dp를 채워주면 된다.

풀이 방법

이중 for문을 통해 dp[1]부터 dp[N]까지 구해준다. 예를들어 dp[4]의 경우에는
dp[1] + dp[3] or dp[2] = dp[2] 두가지 경우의 수가 존재한다. 이를 이중 for문을 통해 1, N까지 and 1, i까지 설정해주면 된다.

즉 점화식은 dp[i] = max(dp[i], dp[i-j] + 해당 카드 값)

풀이 코드

N = int(input())

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

for i in range(1, N+1):
    for j in range(1, i+1):
        dp[i] = max(dp[i], dp[i-j]+cards[j-1])

print(max(dp))

사족

N-1까지 고려했을 떄 dp[N-1] + dp 무언가 하면 되는거 아닌가? 생각했는데... 머릿속으로 고민해봐도 dp[N-1]이 딱히 고려가 되지 않는 거 같아서 다른 방식을 생각했다.
그리고 dp라서 모든 경우의 수를 볼 것이라고는 생각도 못했다...

p1까지 고려했을때 최대값, p2까지 고려했을 때 최댓값... 엉뚱한 방식으로 접근해서 완전 꼬여버렸다.