[구름톤 챌린지] 통증 (2)
풀이 과정 먼저, 이 문제는 Dynamic Programming으로 해결할 수 있다. 예를 들어, 3, 4, 5 힐 아이템이 있다고 가정하고, 9라는 통증을 0으로 만들어야하는 상황을 가정해보자. 그 때, 3원의 동전으로 통증 3을 해결하는 방법은 1가지이고, 통증 6을 해결하는 방법은 통증 (6 - 3)을 해결하는 경우의 수 + 1 즉, 2가 된다. 그리고 마지막 통증 9를 해결하기 위해서는 통증 (9 - 3)을 해결하는 방법 + 1이 된다. 다시 4원과 5원을 봤을때 통증 4를 해결하는 방법, 통증 5를 해결하는 방법은 각각 1가지가 되고, 통증 9를 해결하는 방법은 통증 (9 - 4)를 해결하는 방법 + 1(본인) 즉, 2가지가 필요하다. 따라서 정답은 2가 된다. 이를 순서대로 다시 작성해보자. ..
2023. 8. 31.
