[백준 BOJ / Python] 2293번 동전 1

문제

n가지 종류의 동전이 있다. 각 동전의 가치가 제시될 때, 그 가치의 합이 k원이 되도록 하는 경우의 수를 구하는 문제이다.
이때 순서가 달라도 구성이 같다면 같은 경우의 수이다.

풀이

• 이 문제는 dp를 사용해 풀 수 있다.
• 가치의 합이 k원(1 ≤ k ≤ 10,000)이 되도록 하는 경우의 수 문제를 나누어
• 가치의 합이 y(1 ≤ y ≤ k)가 되도록 하는 경우의 수를 구하는 부분 문제로 볼 수 있다.
• 동전 x1을 사용하여 y가 될 수 있는 경우가 성립하는지 확인하는 것이다.
• 다시 말해 y - x1을 만들 수 있는 조합이 있다면 해당 경우의 수만큼  x1을 가지고 y값을 만들 수 있다.
• 이를 통해 다음과 같은 식을 세울 수 있다.
  dp[y] = dp [y] + dp [y-x1]

 

알고리즘

1. dp 리스트를 만들어준다.
   • 이때 0의 값은 1로 초기화한다. (dp[0] = 1)
   • 1번 출현하는 경우의 수를 1로 만들 수 있게 하기 위함이다.
   • 예를 들어 값이 1인 동전이 있을 때, y값 1을 만들 수 있는 경우의 수를 1로 만들 수 있다.
     dp[1] = dp[1] + dp[0] = 0 + 1 = 1
2. 동전들을 순회하면서 현재 동전이 y값을 만들 수 있는지 경우의 수를 구한다.
   • 앞서 y-x 값을 만들 수 있다면 dp[y-x] = a 값을 dp[y]에 더하면 된다.
     x값까지 포함해 y값을 a개 조합으로 더 만들 수 있다는 의미이기 때문이다.
   • y-x 값을 만들 수 없다는 의미는 dp[y-x] = 0이라는 것이기 때문에, 결국 증가하는 경우의 수는 없다.
3. 최종적으로 dp의 k번째 값을 출력하면 k값을 만들 수 있는 경우의 수가 된다.

 

Python 코드

import sys
input = sys.stdin.readline

n, k = map(int,input().split())
coins = [int(input()) for _ in range(n)]
dp = [0] * (k+1)
dp[0] = 1

for x in coins:
    for y in range(x,k+1):
        dp[y] += dp[y-x]
print(dp[k])

 

문제출처

2293번: 동전 1