BOJ - 2293) 동전 1

특정 금액을 다른 가치를 가진 동전으로 나타낼수 있는 최대 경우의 수를 구하는 문제이다. 기본적인 유형의 동적 프로그래밍 문제이다. 2중 for 문을 사용하여, 주어진 동전의 가치만을 사용할 때의 경우만 생각하며 일정 금액보다 사용할수 있는 동전의 가치가 낮은 경우, 동전의 가치를 뺀 경우의 수를 더하여 갱신함으로써 문제를 해결한다. 

ex) 4원을 위의 예제 입력으로 나타내는 경우, 예제의 1원만 사용할 경우를 생각하여 배열에 값을 갱신한다.

i = 1)  d[1]~d[4] = 1

i = 2)  d[1] = 1, d[2] 의 경우 입력된 동전의 가치보다 크거나 같기 때문에, 기존의 d[2] 배열에 가지수를 추가하여 준다.

         d[4] = d[4](1로만 나타낸 경우의 수) + d[2](1과 2, 2로만 나타낸 경우의수) = 3 으로 값이 갱신된다.