[백준] 2294 - 동전 2

보자마자 다이나믹 프로그래밍으로 풀어야겠구나 생각했던 문제이다.

n = 3, k = 7, 동전은 2, 5, 7가 있다고 가정했을 때를 살펴보자.

 

k	0	1	2	3	4	5	6	7
동전 개수	0	inf	inf	inf	inf	inf	inf	inf

 

2, 5, 7의 가치를 가진 동전으로는 k == 1을 만들 수 없으므로 계속 inf이다.

 

k	0	1	2	3	4	5	6	7
동전 개수	0	inf	1	inf	inf	inf	inf	inf

 

2의 가치를 가진 동전으로 k == 2를 만들 수 있으므로,

cache[2]는 cache[2 - 2] + 1과 cache[2] 중 작은 수인 cache[2 - 2] + 1 = cache[0] + 1 = 1이 된다.

이런 식으로 cache를 채워나가면,

 

k	0	1	2	3	4	5	6	7
동전 개수	0	inf	1	inf	2	1	3	1

 

다음과 같이 각 k별로 동전 가짓수의 최솟값 테이블이 완성된다.

k == 7일 때의 동전 가짓수 최솟값은 1이므로 정답은 1이다.

 

이 과정을 코드로 나타내면 다음과 같다.

n, k = map(int, input().split())

# 동전 목록
board = [int(input()) for _ in range(n)]
cache = [0] + [float("inf")] * k

# bottom-up 방식으로 k가 1일 때부터 15일 때까지의 최소 동전 가짓수 채우기
for i in range(1, k + 1, 1):
    for j in board:
        if(i - j >= 0):
			# j에 해당하는 동전 가치를 뺀 가짓수 + 1과 현재 i에 해당하는 가짓수를 비교
            cache[i] = min(cache[i], cache[i - j] + 1)

# k를 만들 수 있는 동전의 최소 가짓수 출력 / 불가능할 경우 -1 출력
print(cache[k] if cache[k] != float("inf") else -1)