2293: 동전 1

풀이 시간

• 1h
• dp문제 오랜만에 풀었는데 점화식 세우기 + 세운 점화식 구현하기는 여전히 너무 어렵다

구현 방식

• dp[i]에서, i는 가치의 합이고, dp[i]는 가치의 합이 i가 되는 경우의 수이다

문제에서 주어진 조건으로 예를 들자면

1. 처음에 1원짜리 동전만을 이용하여 1원부터 K원까지 만드는 경우를 채워준다.
2. 이제 1원짜리 동전으로 만드는 경우는 채워진 상태이므로 2원짜리 동전을 추가하여 만드는 경우를 채워준다. 이 경우에서는 2원 이상의 경우부터 채울 수 있다.
3. 이제 1원짜리 동전과 2원짜리 동전으로 만드는 경우는 채워진 상태이므로 5원짜리 동전을 추가하여 만드는 경우를 채워준다. 이 경우에서는 5원 이상의 경우부터 채울 수 있다.

• 이 과정에서 2원짜리 동전을 추가하여 만드는 경우를 보면,
  가치의 합 2: 2원
  가치의 합 3: 2원
  가치의 합 4: 2원 + 2원
  가치의 합 5: 2원 + 2원
  가치의 합 6: 2원 + 2원 + 2원
  가치의 합 7: 2원 + 2원 + 2원
  가치의 합 8: 2원 + 2원 + 2원 + 2원
  ...
  이런식으로 2원짜리 동전이 추가가 된다. 2원짜리 동전이 하나 추가 될때마다 경우의 수가 하나 늘어나게 된다.

• 5원짜리 동전을 추가하여 만드는 경우를 보면,
  가치의 합 5: 5원
  가치의 합 6: 5원
  가치의 합 7: 5원
  가치의 합 8: 5원
  가치의 합 9: 5원
  가치의 합 10: 5원 + 5원
  가치의 합 11: 5원 + 5원
  ...
  이런식으로 5원짜리 동전이 추가가 된다. 5원짜리 동전이 하나 추가 될때마다 경우의 수가 하나 늘어나게 된다.

따라서 점화식은 dp[j] = dp[j] + dp[j - coin[i]]가 되게 되고,
이러한 점화식을 코드로 구현하면 아래와 같다

for i in range(N): #i는 coin의 index
    for j in range(coin[i], K+1): #j는 가치의 합, dp[j]는 가치의 합이 j가 되는 경우의 수
        dp[j] += dp[j - coin[i]]

• dp[0]를 1로 설정한 이유는
  -> dp[1] = dp[1] + dp[1 - coin[0]] 이런식으로 될 때, 1원짜리 동전을 이용해 1원을 만드는 경우
  -> dp[2] = dp[2] + dp[2 - coin[1]] 이런식으로 될 때, 2원짜리 동전을 이용해 2원을 만드는 경우
  -> dp[5] = dp[5] + dp[5 - coin[2]] 이런식으로 될 때, 5원짜리 동전을 이용해 5원을 만드는 경우를 위함이다

코드

import sys

N, K = map(int, sys.stdin.readline()[:-1].split())
coin = []
for n in range(N):
    coin.append(int(sys.stdin.readline()[:-1]))

dp = [0 for _ in range(K+1)] #dp[j]는 가치의 합이 j가 되는 경우의 수

dp[0] = 1
for i in range(N): #i는 coin의 index
    for j in range(coin[i], K+1): #j는 가치의 합, dp[j]는 가치의 합이 j가 되는 경우의 수
        dp[j] += dp[j - coin[i]]

print(dp[K])

결과