25일차 - 동전 교환 알고리즘(DP)

DP(Dynamic Programing) : 한번 연산한 결과를 저장해놓고 다시 연산하지 않고 재사용하는 개념.

 

ex) 피보나치 수열

---

아래는 가장 대표적인 동전 교환 알고리즘이다.

새로운 배열을 통해 결과를 저장하고 재사용하면서 구하게 된다.

 

최대 50원, 사용할 수 있는 화폐는 {10,20,50} 3가지 종류일때,

 

1. 최대 값까지의 배열을 만든다.

 

2. 10이 10이될때 경우의 수, 10이 20이될때 경우의 수, 10이 30이 될때 경우의 수, 10이 40이 될때 경우의 수 , 10이 50이 될 때 경우의 수 각각 구한다.

 

3. 20이 20이 될때 경우의 수 => 20은 10일 때 경우의 수와  10일 때 경우의 수의 합으로 구할 수 있다.

10과 20이 있을때 20이 되려면 경우의 수 (10,10), (20,0) 두가지가 존재하게 된다.

10만 존재했을때는 (10,10) 으로 한가지만 존재했지만 20도 존재한다면 10일때 경우의 수 한가지와 20이 있을때 경우의 수 한가지가 추가가 되므로 2가지가 되고 2가 된다. 

수식으로 표현하면 원래 배열에 있던 수 1(10일때경우의 수) + 1(배열 [현재까지 최대의 수 - 구하는 현재 수(20)] 의 값)

 

array[3] = array[3]+array[30-20] => array[3] = 1 + 1

array[4] = array[4]+array[40-20] => array[4] = 1 + 2

array[5] = array[5]+array[50-20] => array[5] = 1 + 2

 

array[5] = array[5]+array[50-50]  => array[5] = 3+1

 

public long ocean(int target, int[] type) {
    
    //0번 인덱스는 사용하지 않는다.
    long [] result = new long [target+1];
    
    //아무것도 하지않아도 한가지 경우의 수는 생긴다.
    result[0] =1;

    for(int i = 0; i < type.length; i++){
      for(int j = 1; j <= target; j++){
        //인덱스는 음수 일수 없으니까 자신보다 작은수가 올 수 없다.
        if(j-type[i] >= 0)
          //type[i]의 수가 들어오기 전까지의 경우의 수에다가 현재까지의 수에서 현재 타입 수를 뺀 값의 인덱스로 찾아 더한다. 
          result[j] = result[j] + result[j-type[i]];
      }
    }

    return result[target];


}

• result[j] => 이전의 화폐(i-1)를 기준으로 누적시킨 경우의 수
• result[j - type[i]] => 현재 화폐(i)를 사용하여 만들 수 있는 경우의 수