[DP] 백준 9084: 동전 (Python)

BOJ 9084 동전

💡 처음에 그리디인줄 알고 풀이를 시도했는데 알고보니 DP 문제였다. 많이 어렵지 않은 것 같아서 풀이를 도전하였다.

정답 코드

t = int(input())

for i in range(t):
  n = int(input())
  price = list(map(int, input().split()))
  m = int(input())
  
  dp = [0] * (m + 1)
  dp[0] = 1
  
  for i in price:
    for j in range(m + 1):
      if j >= i:
        dp[j] += dp[j - i]
        
  print(dp[m])

풀이과정

• 입력 예시를 편하게 만들어보자.

3
2 3 5
10

이럴 경우 정답은 4가 나와야한다.

DP 풀이에 취약하기 때문에 본능적으로 표를 직접 작성하기 시작했다.

처음 2원으로 만들 수 있는 경우의 수를 추출한다.
그 후 2원으로 추출할 수 있는 경우의 수 + 3원으로 추출할 수 있는 경우의 수를 한다.

i/m	0	1	2	3	4	5	6	7	8	9	10
2	1	0	1	0	1	0	1	0	1	0	1
3	1	0	1	1	1	1	2	1	2	2	2
5	1	0	1	1	1	2	2	2	3	3	4

3원의 경우의 수를 확인해보자.
2원의 경우 2원 하나로 대체가 되기 떄문에 count는 그대로 1을 가져온다.
그리고 3의 경우 3원 하나로 가능하기 때문에 0 + 1 해서 1이 된다.
4의 경우 2 + 2만 되기 때문에 그대로 가져오고, 5원은 2 + 3으로 1
6원은 2 + 2 + 2, 3 + 3으로 2개가 된다.

이렇게 += 로 쌓아가는 형식이다.
여기서 이제 규칙을 찾아보자.

💡 5원을 예시로 보자. 5원에서 m이 5원인 경우부터 한개가 느는 것을 볼 수 있다. 5원은 2+3으로 추출할 수 있는데 여기서 5 하나로도 처리가 가능해지는 부분이다.

for i in price:
    for j in range(m + 1):
      if j >= i:
        dp[j] += dp[j - i]

여기서 다음과 같은 코드가 가능해진다.

1. i 값은 price에 있는 [2, 3, 5]이다.
2. 만들어야 할 수를 추출해야하기 때문에 0부터 m까지 범위를 잡는다.
3. 위에서 말한 저 분기점부터 j = 5, i = 5인 순간부터
   dp[5] += dp[5 - 5] = 1 + 1 = 2
   dp[6] += dp[6 - 5] = 2+ 0 = 2
   dp[10] += dp[10 - 5] = 2 + 2 = 4

풀이 후기

DP는 워낙 까다롭고 어렵고, 내가 점화식을 잘 못 찾는 유형이라.. 추후에 연습하려고 했는데 어쩌다보니 도전하게되었다.
많이 어려운 문제는 아니었다고 생각하지만
dp[j] += dp[j - i]에서 dp[j - i] 이 부분을 아마 못 찾았을 것 같다.

점화식을 잘 짜는 것이 정말 중요한 것 같다.
DP는 나중에 연습을 해서 눈이 트이게 되면 상당히 흥미로울 것 같다.