[백준 2293번] 파이썬 - 동전 1

http://www.acmicpc.net/problem/2293

2293번: 동전 1

 

# 조건

• n가지 종류의 동전이 있고 각각의 동전이 나타내는 가치는 다르다.
• 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶을 때, 그 경우의 수를 구하시오
• 각 동전은 몇 개라도 사용 가능하다.
• 동전의 구성이 같은데, 순서만 다른 것은 같은 경우

 

# 접근 방법

• 다이나믹 프로그래밍을 이용해서 풀어주면 될 것 같다.
• 가치의 합 +1 만큼의 dp테이블을 만들어 주고 각 가치를 만들 수 있는 경우의 수를 기록해주면 된다.
• 이후, 각 동전을 순회하는데
• 현재 만들 가치가 u인 경우 dp[u] = dp[u-현재동전의 가치] 를 더해주며 테이블을 완성해나간다.
• 즉, 특정 가치를 가진 동전을 사용했을 때의 합 = dp테이블의 인덱스로 사용하여 경우의 수를 늘려간다.

import sys  
sys.stdin = open('input.txt')  
N, K = map(int, input().split())  
  
# 동전 종류 받아주고 dp 테이블 생성  
coin = [int(input()) for _ in range(N)]  
dp = [0 for _ in range(K+1)]  
# 동전을 하나도 사용하지 않는 경우의 수 1로 설정  
dp[0] = 1  
  
# 모든 가치의 동전을 순회하는데  
for i in coin:  
    # 동전의 가치가 5인 경우 1234는 고려할 필요 없으므로 i로 시작해준다.  
    for j in range(i, K+1):  
        # 현재 만들고자 하는 값 =  현재동전의 가치만큼 뺀 값 + 1  
        dp[j] += dp[j-i]  
  
print(dp[K])