[백준 DP] 2293 동전1

🥕 [ 백준 2293 ] 동전 1

문제 링크

url : https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

🍒 문제 분석

동전의 종류 n과 이를 이용해 만들어야하는 k원이 주어진다.

그리고 각 동전의 단위가 몇인지 알려준다. 이를 통해 k원을 만드는 경우의 수를 구해야한다.

 

가령 n = 3, k = 5 , 동전의 종류가 [1, 2, 5] 라면

1원 짜리 5개

1원 짜리 3개, 2원 짜리 1개

1원 짜리 1개, 2원 짜리 2개

5원 짜리 1개   

하여 4가지 종류가 나온다.

 

🥑 코드 

def sol(k):
    d = [0]*10001
    for coin in coin_list:
        for i in range(1,k+1):
            if coin == i :
                d[i] += 1
            elif coin < i :
                d[i] += d[i-coin]
    return d[k]

n, k = map(int, input().split())
coin_list = [int(input()) for _ in range(n)]

print(sol(k))

 

🍓 내 해결 과정

처음에는 이렇게 생각하였다. (오답)

만들어야 하는 값이 m 이고, 코인의 종류가 1, 2, 5 라고 할 때

(m을 만들어야 하는 경우의 수) = (m-1 의 경우의 수) + (m-2 의 경우의 수) + (m-5 의 경우의 수)

그러나 이렇게 코드를 구현하면 중복되는 경우가 다 더해져 값이 기대하는 값보다 커지게 된다.

 

가령 1 + 1 + 2 와 1 + 2 + 1 은 같은 경우이나 다른 경우로 여겨져 다 더해지게 되는 것이다.

 

 

점화식을 2차원 테이블로 생각해서 접근하기 ( 정답 )

( 가로축 수열과 세로축 수열을 모두 생각한 점화식을 구성 )

 

가로축 수열 : 만들어야 하는 값의 가치가 1 씩 추가됨에 따라 나오는 경우의 수

세로축 수열 : 코인의 종류를 1씩 추가해 감에 따라 나오는 경우의 수

 

coin \ i	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	2	3	3	4	4	5	5	6
5	1	2	2	3	4	5	6	7	8	10

 

2 차원으로 문제를 재구성하면 다음과 같다. ( coin은 화폐 종류,  i는 만들어야 하는 값 )

 

먼저 coin 1 밖에 없다고 하자.

i = 1 은 1원 짜리 한 개로 만들 수 있다.

i = 2 는 i = 1 일 때의 케이스에 1을 덧붙이면 된다. 따라서 경우의 수는 1개이다.

i = 3 은 i = 2 일 때의 케이스에다가 1을 덧붙이면 된다. 따라서 경우의 수는 마찬가지로 1개 이다.

i = ...

i = 10 일때도 마찬가지 이유로 경우의 수는 1이다.

 

이제 coin 2 가 주어졌다고 하자.

i = 1 의 경우 coin 2 로는 만들 수 없으므로 그대로 경우의 수는 1 이다.

i = 2 의 경우 coin 2 하나로 만들 수 있는 경우의 수가 추가 되어 2가 된다.

i = 3 의 경우 i = 1 의 케이스에서 coin 2를 덧붙이면 된다. 따라서 i = 1 일 때의 경우의 수가 더해져 2가 된다.

i = 4 의 경우 i = 2 의 케이스에서 coin 2를 덧붙이면 된다. 따라서 i = 2 일 때의 경우의 수를 더해  3이 된다.

...

i = n 의 경우 i = n-2 케이스를 추가적으로 더하면 된다.

 

이제 coin 5가 주어졌다고 하자.

i = 1 은 그대로

...

i = 4 는 그대로

i = 5 일 때 coin 5 하나로 만들 수 있으므로 1이 더해져 4가 된다.

i = 6 일 때 i = 1 의 케이스에 coin 5 하나를 덧붙이면 된다. 따라서 i = 1 일 때의 경우의 수가 더해져 5가 된다.

...

i = n 의 경우 i = n-5 의 케이스가 추가적으로 더해진다.

 

 

이제 이를 코드로 구현하였다.

 

 

 

🍉 깨달은 점 및 정리

2차원 형태로도 점화식을 생각할 수 있음을 알게 되었다.

 

사실 systemetic 하게 문제를 풀어내었기 때문에

문제를 완전히 통찰하여 풀었다라고는 말할 수 없을 것 같다.

 

앞으로 문제를 풀 때 있어서 1차원적인 접근에서 벗어나 생각할 수 있게 되어 기쁘다.