DP-Coin Change Algorithm 코인 체인지 알고리즘!

Dynamic Programmming(동적 계획법)이란 

복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방식을 의미합니다.

 

동적 계획법을 구현하는 방법 중의 하나가 바로 coin change algorithm(동전 선택 알고리즘) 입니다!

어떻게 코드로 구현하는 지, 어떠한 경우에 사용되는지 한 번 알아보겠습니다. ☺️

 

1. 코드 구현

 

//amount원 만큼을 coins[]에 있는 coin들을 사용하여 만들 수 있는 조합의 수를 구하는 method
public static long change(int amount, int[] coins) {
      
     //조합의 수를 저장할 array 생성
     long[] combinations = new long[amount + 1]; //0부터 amount까지의 숫자가 모두 들어가야 해서 size는 amount+1이 됨
 
     //0번째는 무조건 1
     combinations[0] = 1;
 
     //coins[]에 담긴 coin 하나씩 사용하여 만드는 조합의 수 카운팅하기
     for(int coin : coins) {
         for(int i = 1; i < combinations.length; i++) {
             //i가 coin보다 커질 때, 새로운 조합이 나타나게 됨
             if(i >= coin) {
                 //그러므로 i에는 새로운 조합 추가!
                 combinations[i] += combinations[i - coin];
             }
         }
     }
     return combinations[amount];
}