Coin Change

문제: COIINS / 동적계획법 (DP)

[ 해결전략 ]

 

10, 50, 100원으로 110원을 만드는 경우를 생각해보자.

• 10x11
• 10x5+50x1
• 50x2
• 10x1+100x1

이렇게 네 가지 경우이다. 더 작게 생각해보면 50원을 만들 수 있는 방법은 2가지 (10x5, 50원 자기자신) 이다.

여기서 어렵게 느껴지는 부분은 모든 경우의 수를 다 고려해야 한다는 점이다.

즉, 10원을 한 번 사용해보고(10원), 두 번 사용해보고(20원), 세 번 사용해보고(30원)...

만드려는 금액이 110원보다 작은 범위에서 모든 조합을 시도해봐야 한다. 동전의 종류가 많아진다면? 

일일이 조합해서 카운트 하는 방법으로는 문제를 해결할 수 없다.

여기서 어떤 사실을 고려해야 하는지 생각해보면 실마리를 잡을 수 있다.

먼저 10원만 사용한다고 생각해보면 20원을 만들 수 있고 30원을 만들 수 있고.. 110원까지 만들 수 있다.

다음으로 50원을 사용해보자. 이 때 10원만 사용해서 만든 정보를 이용한다.

50(자기자신), 50+10=60, 50+20=70, 50+30=80... 이 합이 의미하는 것은 10원과 50원을 이용해서 만들 수 있는 금액이다.

이 과정에서 50을 만들 수 있는 가지 수는 2가 된다(10x5, 50x1). 60을 만들 수 있는 가지 수는? 역시 2가 된다.

이 과정을 배열로 표시해보면 어떻게 될까? 금액을 배열의 index로 사용하고 

그 값은 index에 해당하는 금액을 만들 수 있는 가지 수로 표현해보는 것이다.

// cost => 현재 사용 중인 동전의 가치(금액)

// i => 이전에 사용했던 동전들로 만들 수 있었던 금액

// i+cost => 현재 만들 수 있는 금액

array[i+cost] += array[i];

이전에 사용했던 정보들을 이용해서 값을 누적시키는 방법이므로 DP(Dynamic Programming)에 해당하는 문제이다.

코드: https://github.com/xgate/algospot/blob/master/DP/COINS.cpp