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

백준 2293번 동전 1 - 파이썬 풀이

< 목차 >

1. 문제풀이 아이디어
2. 구현코드

문제풀이 아이디어

• 해당 문제는 이전의 수의 풀이 값을 이용하여 현재의 수에 대한 값을 구하기 때문에 DP 문제이다.
• 먼저 해당 문제를 굉장히 간단하게 1,2의 동전 종류로 4의 값을 만든다고 가정해보자.dp = [0]*(k+1)

동전 종류	1	2	3	4
1
2

• 위의 표를 이용해서 설명을 하면 동전 종류 1을 이용해서 1이란 수를 만들기 위한 경우의 수는 몇개일까? 1개일 것이다. -> [1] 
• 그렇다면 동전 종류 1을 이용해서 2이란 수를 만들기 위한 경우의 수는 몇개일까? 1개일 것이다. -> [1,1]
• 그렇다면 동전 종류 1을 이용해서 3이란 수를 만들기 위한 경우의 수는 몇개일까? 역시 1개일 것이다. -> [1,1, 1]
• 그럼 이번에는 다르게 동전 종류 2를 이용해서 1을 만드는 경우는 당연히 0개일 것이고 2를 만드는 경우는 몇개일까? 1개일 것이다. -> [2]
• 그럼 동전 종류 2를 이용해서 3을 만드는 경우는 당연히 1개일 것이다. -> [1,2]
• 그럼 동전 종류 2를 이용해서 4를 만드는 경우는 ?? 2개이다. -> [1,1,2], [2, 2]
• 여기서 4에 대한 부분을 잘 생각해보자. 4를 만들기 위한 총 경우의 수는 [1,1,1,1], [1,1,2], [2, 2] -> 3개이다.
• 그럼 4에 대한 경우는 1을 이용해서 4를 만든 경우와 1,2를 이용해서 2를 만들고 거기에서 2를 이용해서 4를 만든 경우로 나뉜다.
• 만약 여기서 순서를 고려해서 만든다면 모든 경우를 구하겠지만 이 경우엔 순서를 고려하지 않기 때문에 중복한 경우를 버리기 위해서 동전의 종류 하나씩 반복을 하면서 경우의 수를 구해나가는 것이다. 1을 이용한 경우의 수를 구했으니까 2를 이용한 경우를 구하면서 4를 구할땐 앞에 1,2를 이용한 모든 조합에 2를 추가함으로써 4로 도달할때 2를 이용하게 하는 것이다.

동전 종류	1	2	3	4
1	1	1	1	1
2	0	1	1	2

구현코드

if __name__ == "__main__":
    n, k = map(int, input().split())
    coin = [int(input()) for _ in range(n)]

    dp = [0]*(k+1) 
    dp[0] = 1
    for c in coin: # 동전의 종류 -> 반복.
        for num in range(k+1): # k+1까지 값을 올리면서 해당 동전의 종류로 구성되는 경우의 수를 구함.
            if c <= num: # 동전의 종류 값보다 작으면 경우의 수는 0
                dp[num] += dp[num-c] # 현재 값에 동전의 종류를 마지막에 이용해서 도달할 수 있는 경우
    print(dp[k])