[백준 DP] 2294 동전 2

🥕 [ 백준 2294 ] 동전 2

문제 링크

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

2294번: 동전 2

 

🍒 문제 분석

n 가지 종류의 동전이 있다. 이 동전들을 적당히 사용해 가치의 합이 k원이 되도록 만들고 싶다.

그러면서 동전의 갯수를 최소로 하고 싶다. 이때 사용하는 최소의 동전 갯수를 구하여라.

 

🥑 코드

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

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

 

🍓 내 해결 과정

 

coin \ value	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1 (index = 0)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5 (index = 1)	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3
12(index = 2)	1	2	3	4	1	2	3	4	5	2	3	1	2	3	3

 

coin = 1 만 있을 때,

coin = value : dp[value][0] = 1

 

coin =5 가 추가 될 때,

coin > value : dp[value][1] = dp[vaue][0]

coin = value : dp[vaue][1] = 1

coin < value : dp[value][1] = min( dp[value - coin][coin] + 1, dp[value][0] )

 

coin = 12 가 추가될 때,

coin > value : dp[value][2] = dp[value][1]

coin = value : dp[value][2] = 1

coin < value : dp[value][2] = min( dp[value-coin][coin] + 1 , dp[vaue][1] )

 

이를 코드로 구현

 

 

다음의 방식을 써도 되는 이유는

n = value 에서 n 의 값에 관계 없이 모든 점화식이 성립하기 때문이다.

 

가령 예시에서 value가 15일 때,

 만약 dp[value][1] 이 dp[value-coin][coin] + 1 보다 작다면,  value 가 27일 때도 마찬가지일 것이기 때문이다.

( 만약 12를 안쓰는 것이 더 낫다면 이후에도 12를 안쓰는 것이 낫다는게 다음의 이유이다. )

 

다시 말해 다이나믹 프로그래밍이 적용 가능한 상황이다.

 

🍉 깨달은 점 및 정리

동전 1에서 배운 깨달음을 그대로 동전 2에 써먹었다.

점화식으로 도출할 수 있다는 말은 곧 dp가 적용된다는 소리이다.

점화식은 위와 같이 2차원 테이블로도 접근 가능하다.