백준(BaekJoon) 2293번 : 동전 1 - python 풀이

JISU LIM·2023년 1월 2일

Algorithm Study Records

목록 보기

3/79

❓2293번 : 동전 1

〽️ 문제 요약

n가지 종류가 주어질 때 k원을 만드는 경우의 수를 구하면 되는 문제

🤨 접근법

본 접근법은 여기를 참고했음을 밝힙니다.

동적 계획법(Dynamic Programming; DP)은 최적화 문제를 해결하는 알고리즘으로

‘전체 문제’를 ‘부분 문제’로 잘 나누었는가? 그렇다면 전체 문제를 해결하기 위한 부분 문제의 점화식은 무엇인가?
부분 문제들을 해결하며 얻는 결과값을 메모이제이션(테이뷸링)하는가?
부분 문제의 점화식은 부분 문제들 사이의 관계를 빠짐없이 고려하는가?

를 항상 명심해야 한다.

이 문제에 대해 DP로 접근하는 방식의 기본이 되는 것은 바로 k원을 만드는 경우의 수를 구하는 전체 문제를 j(1 ≤ j ≤ k)원을 만드는 경우의 수를 구하는 부분 문제로 나누는 것이다.

또한 여기에는 동전 N(1 ≤ N ≤ n) 종류로 i원을 만드는 경우의 수를 구하는 부분 문제도 포함되어 있다.

Untitled

위 예제에 대해 살펴보면

먼저 1원으로 1~10원을 만드는 경우의 수는 각 1가지 씩이다

N	0	1	2	3	4	5	6	7	8	9	10
[1]	1(0)	1	1+1	1+1+1	1+1+1+1	1+1+1+1+1	1+1+1+1+1+1	1+1+1+1+1+1+1	1+1+1+1+1+1+1+1	1+1+1+1+1+1+1+1+1	1+1+1+1+1+1+1+1+1+1

이제 여기에 2원과 5원을 사용할 수 있게 되면 추가되는 경우의 수가 추가된다.

Untitled
출처 : https://mong9data.tistory.com/68

이 과정까지 본다면 규칙을 찾아낼 수 있는데, 동전 1로만 2를 만들어내는 경우의 수에서 2 동전을 사용할 수 있을 경우 경우의 수가 2 동전 1개를 사용하는 경우 하나가 다음과 같이 추가된다.

1+1 (동전 2를 0번 사용하는 경우)
2 (동전 2를 1번 사용하는 경우)

다음 동전 1로만 3을 만들어내는 경우의 수에서 2 동전을 사용할 수 있을 경우 경우의 수는

1+1+1 (동전 2를 0번 사용하는 경우)
1+2 (동전 2를 1번 사용하는 경우)

다음 동전 1로만 4를 만들어내는 경우의 수에서 2 동전을 사용할 수 있을 경우 경우의 수는

1+1+1+1 (동전 2를 0번 사용하는 경우)
1+1+2 (동전 2를 1번 사용하는 경우)
2+2 (동전 2를 2번 사용하는 경우)

이때 2를 만들어 내는 경우의 수 입장에서 생각해보면 1+1로 2를 만드는 경우의 수에서 2 동전 하나를 사용해 4를 만드는 경우와 , 2로 2를 만드는 경우에서 2 동전 하나를 사용해 4를 만드는 두 가지 경우가 기존 1로만 4로 만드는 경우에 하나에 추가된다.

다시 말하면 위 과정을 다음과 같이 쓸 수 있다.

$f_{new}(4) = f(4)+f_{new}(2)$

여기서 $f_{new}$ 는 새로운 동전을 추가 사용했을 때 경우의 수, $f$ 는 기존 동전만을 사용했을 때 경우의 수를 의미한다. 기존 동전만을 사용했을 때 경우의 수에 새로운 동전을 하나씩 추가하는 경우를 tabulation 하는 것이다. 다시말해, 기존 경우에서 i원짜리 동전을 새로 사용한다면 k원을 만들기 위해서 i원 동전을 활용하지 않고 k원을 만드는 경우에 i원 동전을 활용해서 k-i원을 만드는 경우를 더해준다.

$f_{new}(k) = f(k)+f_{new}(k-i)$

🔡 코드

import sys

input = sys.stdin.readline

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

for coin in coins:
    for j in range(1, k+1):
        if j-coin >= 0:
            dp[j] += dp[j-coin]

print(dp[k])