보자마자 다이나믹 프로그래밍으로 풀어야겠구나 생각했던 문제이다.
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)
'Study > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준] 11727 - 2xn 타일링 2 (0) | 2024.08.13 |
---|---|
[백준] 11726 - 2xn 타일링 (0) | 2024.08.12 |
[백준] 1463 - 1로 만들기 (0) | 2024.08.11 |
[프로그래머스] 2019 카카오 겨울 개발 인턴십 - 튜플 (0) | 2023.04.04 |
[백준] 9663 - N-Queen (0) | 2023.01.17 |