2294 (1) 썸네일형 리스트형 [백준] 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 동전.. 이전 1 다음
