[DP] Coin Change

coins배열의 원소들을 합하여 amount로 입력된 값을 만들려고 한다.(원소들은 중복 사용이 가능하다)

이때 만들 수 있는 갯수가 가장 적은 케이스를 찾아 해당 갯수를 리턴한다. 

만드는것이 불가능하다면 -1을 리턴한다. 

전형적인 DP문제로, amount만큼을 갯수로 가진 배열을 만들어 각 부분의 solution을 구해 global과 비교하면 된다.

 

dp라는 배열을 만들고 amount가 0일때의 값을 입력한다.

그 뒤, 0부터 amount까지에 대한 Loop를 돌면서 coin의 각 원소와 비교한다

 

예컨데 [ 1, 2, 5 ]인 coins에 대해 i가 5라고 해보자.

일단 coin이 i보다 커지면 의미가 없으므로, i는 coin보다 항상 크거나 같아야 한다.

이 조건을 만족하는 경우에 대해, 해당 coin 값을 뺀 local solution에 1을 더한 것중 최소 값을 구한다.

모든 dp[ i ]에 대한 값을 차곡차곡 구해서 amount를 구하면 된다.