[BOJ] Q2293 동전 1

[BOJ] Q2293 동전 1

Question

Language: Python

Difficulty: Gold 5

주어진 동전의 종류를 활용해서 k원을 만들고자 할때, k원을 만들 수있는 동전 조합의 개수는?

문제의 예저를 통해서 알아보자

	1	2	3	4	5	6	7	8	9	10
1 이용했을때	1	1+1	1+1+1	1+1+1+1	1+1+1+1+1	1+..	1+..	1+..	1+..	1+..
2 이용했을때	1	1+1,2	1+1+1,1+2	1+1+1+1,1+1+2,2+2	1+1+1+1+1,1+1+1+2,1+2+2	..	..	..	..	..
5 이용했을때	1	1+1,2	1+1+1,1+2	1+1+1+1,1+1+2,2+2	1+1+1+1+1,1+1+1+2,1+2+2,5	..	..	..	..	..

잘 보면 규칙성이 보인다

5원을 만들때의 경우를 보자

1을 이용했을때, 5-1(4)원을 만드는 경우에 1을 더하면 5가 된다. 2을 이용했을때, 5-2(3)원을 만드는 경우에 2을 더하면 5가 된다. 5을 이용했을때, 5-5(0)원을 만드는 경우에 5을 더하면 5가 된다.

각각 k 원에 대해 아래의 DP 연산을 진행하면 된다.

Logic

for money_type in money_types:
  for i in range(k):
    if i-money_type >=0:
      dp[i]+=dp[i-money_type]

Solution

def solution():
    dp=[0] * (k+1)
    dp[0]=1
    for money_type in money_types:
        for i in range(1,k+1):
            prev_step=i-money_type
            if prev_step >=0:
                dp[i]+=(dp[prev_step])

    print(dp[k])    
    
if __name__ =="__main__":
    n,k=map(int,input().split())
    money_types=[]
    for _ in range(n):
        money_types.append(int(input().strip()))
    solution()