Min coin chanllenge

• Reference
• 주어진 동전들로 주어진 합을 만들기위한 최소 동전 개수를 구하는 문제다.

Algorithm

[2, 3, 5], sum = 11

• 합이 11로 만들기 위한 동전이 2, 3, 5 원을 구성해서 만들 수 있는 최소 동전 수를 구해야된다.
• F(11) = 1 + Min(F(9), F(8), F(6)) 이런식으로 점화식을 바로 떠올려야된다.
• 연습을 해보더라도 이전에 Basic에서 공부했던대로 Sub 문제가 여러개 겹치고, 큰 문제를 해결할 수 있다는 감을 잡아야한다.

0  1  
0 -1

• 동전으로 0을 만드는 경우 특수한 경우로 판단해서 0개, 1의 경우 동전이 없으므로 불가능한 경우에대해서는 -1로 둔다.

F(2) = 1 + Min(F(0), F(-1), F(-3)) = 1 (-1은 유효한 숫자가 아니므로 Min 값으로 취급 하지 않는다.)

• 위의 방식대로 그대로 Bottom -up 으로 해결하면 Time Complexity O(nxk) , Space Complexity O(n) 이된다.
  • k는 Min을 구하는데 사용되는 연산 횟수다.