쉬우면서도 어려운 그것...

11052: 카드 구매하기

1. 내 풀이: 성공

import sys

N = int(sys.stdin.readline())
d = [0] * (N+1)
P = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
d[1] = P[1]

for i in range(2, N+1):
    for j in range(1, i+1):
        if d[i] < d[i-j] + P[j]:
            d[i] = d[i-j] + P[j]

print(d[N])

일단 다이나믹 프로그래밍이 나에게 어려운 이유:

1. 규칙 찾기가 너무 어렵다
2. 규칙 찾기가 꽤나 어렵다
3. 규칙 찾기가 제일 어렵다

라는 것이다 ^^ ~

규칙만 찾으면 금방 구현할 수 있는데 (당연한 소리) !
사담은 이만 줄이고 풀이를 설명해보겠다.

2가지의 리스트를 선언해주었다.

• d : 구매하려고 하는 카드 개수에서의 최댓값
  -> 이를 테면, d[2]의 경우 2개를 구매할 때 나올 수 있는 최댓값을 의미한다.
• P : 카드 한 묶음의 값들 (1개의 값부터 N개의 값)

이때 모든 리스트에 0을 추가해주었다. 예를 들어, d[1]은 2개를 구매할 때 나올 수 있는 최댓값이 아닌, d[2]에서 2개를 구매할 때 나올 수 있는 최댓값을 직관적으로 나타내기 위함이다.

이 다음의 규칙이 중요하다.

• n=2일 때, n의 최댓값: d[2] = d[1] + p[1] or d[0] + p[2]
• n=3일 때, n의 최댓값: d[3] = d[2] + p[1] or d[1] + p[2] or d[0] + p[3]

이 과정은 따지고 보면 n을 1부터 n까지 쪼개서 각 값을 다 더하는 것과도 유사하다고 할 수 있다.

2. 다른 풀이

이 문제에서 나올 수 있는 점화식은

d[i] = P[k] + d[i-k]

이므로 드라마틱한 다른 풀이가 있지는 않다. 다만 for문의 구현 방식이 조금씩 다를 뿐...! 아래 풀이의 출처는 다음과 같다.
https://infinitt.tistory.com/250

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

오늘도 신기한 알고리즘의 세계 끝!