백준 11052 : 카드 구매하기 (파이썬)

다이나믹 프로그래밍 알고리즘을 활용하는 문제이다.

 

DP 문제는 기초가 되는 점화식을 정확하게 세우면 문제가 쉽게 풀리는데, 계속 머릿속으로만 코드를 구성하려고 애쓰다보니 문제가 잘 안풀렸다.

대략적인 흐름을 dp[4] 정도까지만 노트에 써보면서 흐름을 파악하니 어느 정도 윤곽이 나오는 것을 보고, 잘 안풀리는 문제가 있으면 머리로 애쓸것이 아니라 노트에 써가면서 눈으로 흐름을 파악해야 된다는 것을 깨달았다.

(나는 폰 노이만이 아니요)

 

DP 문제에 대해 스스로 부족함을 많이 느끼고 있기 때문에 나 자신을 설명시킬 겸 최대한 상세하게 뜯어가면서 설명했다.

이번 문제에 대한 점화식의 유도 과정을 아래에 써보았다.

---

내가 현재 카드 한 개를 가지고 있다고 생각하는 것에서 출발해보자.

왜냐하면 한 개를 살 때의 최선은 그냥 한 개를 새로 사는 것이기 때문이다. 즉,

 

P[1]
 = dp[1]

 

그러한 상태일 때 추가로 카드 하나를 더, 즉 카드 두 개를 구입할 수 있을 때 최선은...

 

• 기존 것을 포기하고 두 개가 들어있는 카드팩 하나를 새로 구매할 것인지,
• 한 개가 들어있는 카드팩을 추가로 구매할 것인지 정해야 한다.

 

기존 것을 포기한다니 말이 좀 이상한데 식으로 보면 명확하다.

 

max(
P[2],
P[1] + P[1]
)
 = dp[2]

 

그렇다면 카드 세 개를 구입할 수 있을 때의 최선은 어떨까?

일단 하던대로 노가다를 해본다.

 

세 개가 들어있는 카드팩 하나,

두 개가 들어있는 카드팩 하나 + 한 개가 들어있는 카드팩 하나

(정확히는 두 개를 사고 남은 공간에 채울 수 있는 카드팩 하나),

한 개가 들어있는 카드팩 셋,

(정확히는 한 개를 사고 남은 공간에 채울 수 있는 만큼 카드팩을 또 채운다),

 

max(
P[3],
P[2] + P[1],
P[1] + P[1] + P[1]
)
= dp[3]

 

그런데 우리는 이미 앞선 과정을 통해 두 개가 들어있는 카드팩을 고를 때와 한 개가 들어있는 카드팩을 고를 때의 최선의 선택을 배열에 dp[n] 의 형태로 저장해 놓았다.

 

다시 말해 N 장의 카드를 구매할 수 있다고 치면,

 

1. 기존 것을 포기하고 아예 N 장 짜리 큰 카드팩을 새로 살 것인지,
2. N - i 개가 들어있는 카드팩들을 추가로 구매 해가며 카드팩의 구성을 조합할 것인지 정해야 한다.

 

이것은 'N - i 개 만큼 사고 남은 여유 장 수 만큼 기존에 dp 에 저장해둔 최선의 케이스와 조합을 할 것인지 정한다.' 라고도 할 수 있다!

 

단순히 노가다 하듯 어떤 카드를 사고 남은 경우를 따져가며 세는 것보다 각 경우에 따라 취할 수 있는 가장 최선의 선택을 저장해놓고 있기 때문에 훨씬 효율적이다.

(지금은 N 이 손으로 충분히 써 볼 만큼 적기 때문에 일일히 P[1] + P[1] ... P[N] 할 수 있다)

정리하자면, N 장 만으로 구성할 때의 최선의 선택은 dp[N] 인 것이다. 그러니까 저렇게 노가다 할 필요가 없이,

 

 

max(
P[3],
P[2] + dp[1],
P[1] + dp[2]
) 
= dp[3]

 

위와 같이 쓸 수 있다.

 

반복해서 말하고 있지만, dp[n] 은 n 개의 카드를 살 때 가장 최선의 경우를 저장하는 배열이므로,

dp[3] 는 세 개의 카드를 살 때 가장 최선의 경우라 할 수 있다.

 

같은 원리로 카드 네 개를 구입할 수 있을 때,

 

네 개가 들어있는 카드팩 하나,

세 개가 들어있는 카드팩 하나 + (세 개를 샀으니 나머지 여유 공간이) 한 개 일때 취할 수 있는 최선의 선택,

두 개가 들어있는 카드팩 하나 + 두 개 일때 취할 수 있는 최선의 선택,

한 개가 들어있는 카드팩 하나 + 세 개 일때 취할 수 있는 최선의 선택

 

max(
P[4],
P[3] + dp[1],
P[2] + dp[2],
P[1] + dp[3]
)
 = dp[4]

 

N 이 커지면서 이런 모양으로 반복 될 것이다.

 

max(
P[N],
P[N - 1] + dp[1],
P[N - 2] + dp[2],
P[N - 3] + dp[3],
...
P[1] + dp[N - 1]
)
= dp[N]

 

즉 여태까지의 식을 정리하여 써보면,

 

# 카드팩들이 들어있는 리스트 P 에 대해 N 장의 카드를 구매할 수 있는 최선
i = 0
while i < N:
	dp[N] = max(dp[N], P[N - i] + dp[i])
	i += 1

 

기초가 되는 코드는 이렇게 된다.

---

다만 흐름을 파악한 이후에 대략적인 점화식을 세웠는데, 이것이 이중 for 문의 형태를 가지고 있어서 맞나? 싶었다.

DP 문제는 이중 for 문이 잘 안나오지 않나? 라는 알고리즘 뉴비다운 생각과 "틀렸습니다" 공포증 덕분에 빨리빨리 시도해보지 못하고 의심만 하다가 몇 시간이 걸렸다...

 

import sys
N = int(sys.stdin.readline())
P = [0] + [*map(int, sys.stdin.readline().split())]
dp = [0] * (N + 1)
dp[1] = P[1]
for i in range(2, N + 1):
    for j in range(i, 0, -1):
        dp[i] = max(dp[i], P[j] + dp[i - j])
print(dp[-1])

 

다행히 DP 기초 문제이고 주어지는 입력의 양이 이중 for 문으로 실행 할 수 있는 범위에 있었다.

 

DP 문제들은 내 머리로는(ㅠ) 너무 어려운 문제라서 이렇게라도 설명해놓지 않으면 나중에 다 까먹을 것 같다...

다만 공부하면서 DP 적인(?) 발상들이 굉장히 자극이 된다.