2249 동전 2

n개의 가치가 다른 동전을 적절히 사용해서 k 가 되게 하려고 한다. 동전의 수가 무한할 때, 동전의 갯수를 최소로 사용하는 경우의 갯수를 구하는 문제이다.

전형적인 DP 문제이다. 그러나 내 입장에서 DP는 어떤것도 어렵게 느껴진다.

이 문제를 푸는 방법은,
우선 1~k 까지, 각 숫자에 몇개의 동전 갯수가 사용 됬는지를 저장할 배열을 만든다.
그리고 그 배열을 최대값으로 초기화 한다.

또, n개의 동전의 값어치에 해당하는 배열의 위치를 1로 초기화 한다.
동전의 값어치에 해당하는 위치는 동전 1개만 사용하면 만들 수 있기 때문이다.

그다음 한 동전씩 골라서 매번 1~k까지 비교를 한다.
비교 방법은, 현재 숫자에 현재 동전의 값어치 만큼을 더한 숫자의 갯수가, 현재 숫자의 갯수 + 1 보다 크면, 새로운 최소값이 생긴것이기 때문에 값을 갱신한다.
이 때, 오버 플로우 문제가 생기지 않도록 해준다.

반복이 끝난 후, k에 해당하는 배열의 숫자를 출력해주면 된다.

소스