[WEEK04/DAY02] 백준 9084번: 동전

https://www.acmicpc.net/problem/9084

9084번: 동전

DP (다이나믹 프로그래밍)의 대표 문제같은 느낌이다.

 

은행원 한숨 나오는 짤 (사진=뉴시스)

문제 해석 :

T번의 테스트 케이스가 주어지고,

N가지 동전으로 금액 M을 만드는 모든 방법의 수를 출력해야 한다.

 

$N(1 \leq N \leq 20)$개의 동전 종류가 주어진다. 동전은 개수 제한 없이 쓸 수 있다.

동전들의 가치 $N_i (1 \leq N_i \leq 10000)$는 오름차순으로 정렬되어 주어진다.

만들어야 할 금액 $M$은 $(1 \leq M \leq 10000)$범위에 있다.

 

쉽게 생각하면,

주어진 동전들을 적당히 써서 M이라는 금액을 만들면 되는데, 가능한 경우의 수가 모두 몇 가지인지를 알아내면 된다.

 

조합의 문제인가? 라고 생각하기엔 $\to$ 같은 종류의 동전을 무한히 쓸 수 있기에 쉽지 않다.

 

결론부터 말하면 DP 테이블을 사용해서 풀면 되는 문제다. 아래에서 자세히 설명하겠다.

 

 

접근 및 풀이 :

자, 만들어야 하는 금액 M이 15원이라고 가정해보자.

주어진 동전은 3원, 5원이다.

 

우선 전제할 것이 있는데, 0원을 만들기 위해서는 몇 가지의 경우의 수가 필요할까?

0원을 만드려면, 동전을 아무것도 쓰지 않으면 된다.

즉, 한 가지의 경우의 수가 존재한다... 라고 해보자.

 

이제부터 주어진 동전 중에 가장 작은 동전인 3원을 가지고 금액을 만들어 볼 것이다.

안타깝게도 3원으로는 1원, 2원은 만들 수 없다.

동전의 가치가 만들어야 하는 금액보다 크기 때문이다.

 

그러면 3원으로 3원을 만들어보자.

우리는 아까 0을 만들기 위한 방법이 한 가지가 있다는 사실을 알아냈었다.

3원을 한 개 사용하면 나머지 0이 남는데, 0을 만드는 방법은 한 가지가 있으므로

3원을 만드는 방법은 한 가지가 존재하는 것이다.

이것을 테이블로 표현하면 다음과 같다.

0원

1원

2원

3원

4원

5원

6원

7원

8원

9원

10원

11원

12원

13원

14원

15원

1

0

0

1

아직은 얼른 이해가 안 될 것이다. 다음 경우를 보자.

 

3원으로 4원을 만들 수 있는지를 알아보기 위해서는, 3원을 한 번 쓰고 남은 나머지 1에 대해서

1원을 만드는 방법이 있었는지를 보면 된다.

그래서 테이블 인덱스 1을 봤는데... 아쉽게도 없다.

따라서 4를 만드는 방법은 없는 것이므로, 테이블 인덱스 4에 0을 더해준다.

같은 방법으로 찾아봤을 때, 5원도 만들수가 없다.

0원

1원

2원

3원

4원

5원

6원

7원

8원

9원

10원

11원

12원

13원

14원

15원

1

0

0

1

0

0

이제 3원으로 6원을 만들 수 있는지 확인해보자.

3원을 한 번 쓰고, 나머지는 3이 남는다.

그래서 인덱스 3을 보니, 가능한 경우의 수 1이 있다는 정보가 남아있다!

그러므로 인덱스 6에 1을 더해줄 수 있다.

 

이런 식으로 쭉 반복하면 다음과 같은 테이블이 완성된다.

0원	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원	11원	12원	13원	14원	15원
1	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1

이제 5원을 가지고 만들어보자.

 

마찬가지로, 5원으로는 5원보다 작은 금액인 1, 2, 3, 4원은 만들 수가 없다.

따라서 5원으로 5원을 만들 수 있는지 보자.

5원을 한 번 사용하고 남은 0에 대해서 가능한 경우의 수가 있는가?

인덱스 0을 보니, 한 가지가 있다고 기록되어 있다.

인덱스 5에 1을 더해주자.

 

6원 $\to$ 5원을 사용한 나머지인 1을 만들 수 있는 경우의 수 : 0

하지만! 아까 3원을 사용했을 때 6원을 만들 수 있는 경우의 수는 1이었다.

따라서 1에 0을 더해준 1이 남아있다, 라고 이해해야 한다. (누적하는 개념)

 

7원 $\to$ 5원을 사용한 나머지인 2를 만들 수 있는 경우의 수 : 0

 

8원 $\to$ 5원을 사용하고 나머지 3을 만들 수 있는 경우의 수 : 1

그러므로 인덱스 8에는 1을 더해줄 수 있다.

 

이런 식으로 14원까지 채워보자.

0원	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원	11원	12원	13원	14원	15원
1	0	0	1	0	1	1	0	1	1	1	1	1	1	1	1

지금 14원까지는 3원으로 만들 수 있는 경우의 수, 5원까지 써서 만들 수 있는 경우의 수가 다 들어있다.

5원으로 15원을 만들 수 있는지 확인할 차례다.

 

15원에서 5원을 사용한 나머지 10에 대해서, 경우의 수 1이 있다. 따라서 인덱스 15에 1을 더해줄 수 있다.

그런데 아까 3원을 사용해서 15원을 만들 수 있는 경우의 수 1이 있었기 때문에, 거기에 누적해서 1을 더해주는 것이므로

15원을 만들 수 있는 경우의 수는 2가 된다.

 

 

이제 동전을 다 써봤다. 완성된 테이블의 인덱스 15에는 2라는 값이 저장되어 있고,

그것이 최종적으로 우리가 원하는 답 - 3원과 5원으로 15원을 만들 수 있는 경우의 수가 나오는 것이다.

 

과정을 정리하면 다음과 같다.

1. 만들어야 하는 금액 M 만큼의 길이를 가지는 테이블을 만든다.

2. 가지고 있는 가장 작은 동전부터 시작하여, 해당 금액을 만들 수 있는지를 확인한다. 확인하는 방법은 해당 금액($M_i$)에서 동전의 가치($N_i$)를 뺀 나머지에 대해, 가능한 경우의 수가 얼마였는지를 확인해서 가져오면 된다.

3. 모든 동전으로 확인을 마치면, 최종적으로 M원을 만들 수 있는 경우의 수가 테이블 인덱스 M에 남아있게 된다.

 

 

내 글이 좀 부족한 관계로 아직 이해가 되지 않았다면...

정글 선배님인... 아래의 블로그 포스팅을 참고해보길 바란다.

https://d-cron.tistory.com/23

[week04] 백준 9084번 python DP 천천히 이해해보기

 

 

마지막으로 나의 코드를 첨부한다.

import sys
input = sys.stdin.readline
T = int(input())
for i in range(T):
    N = int(input().strip())
    coins = list(map(int, input().split()))
    K = int(input().strip())

    DP_table = [0]*(K+1)
    DP_table[0] = 1

    for j in range(len(coins)):
        c = coins[j]
        for k in range(c, K+1):
            DP_table[k] += DP_table[k-c]

    print(DP_table[K])

P.S.

DP의 특징이라고 느끼는 건데, 생각하는 건 참 어렵지만 생각만 해내면 코드는 참 간결해지는 것 같다.

마스터 하기 위해 열심히 노력하자!