다이나믹 프로그래밍 - 동전1 (백준 2293번)

1. 다이나믹 프로그래밍 - 동전1 (백준 2293번)

---

---

2. 다이나믹 프로그래밍을 이용한 문제풀이

---

package _317324;
 
import java.util.Scanner;
 
public class Baekjoon2293Coin1 {
    static int dp(int[] coin,int[] memo,int n,int k) {
        memo[0]=1;
        for(int i=0;i<n;i++) {
            for(int j=1;j<k+1;j++) {
                if(j-coin[i]>=0) memo[j]+=memo[j-coin[i]];
            }
        }
        return memo[k];
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int[] coin=new int[n];
        int[] memo=new int[k+1];
        for(int i=0;i<n;i++) {
            coin[i]=sc.nextInt();
        }
        System.out.println(dp(coin,memo,n,k));
    }
 
}
 

이 문제를 예를 들어 설명한다면, dp메소드에서 반복문에 들어가게 되면 우선 memo[0]=1 이라고 초기화를 한다. 이 것은 동전을 아무 것도 선택하지 않는 경우를 한 경우로 보고 1로 초기화하는 것이다.(확률에서 선택하지 않는 것도 하나를 1로 생각하는 것과 같다 보면된다.) 그리고 반복문을 들어가게 된다. 여기서 i=0 일때를 보면 j-coin[i]>=0 에서 j=1부터 성립을 하게 된다. 그래서 memo[1]=memo[1]+memo[0] 에서 memo[1]=1 이 되게 된다. 여기서는 coin[1]이 1이므로 k+1까지 모두 1가지 경우로 값이 대입되게 된다. 하지만 2,3 혹은 어느 값이 들어오더라도 그 값의 배수에만 경우의 수 1이 들어가게 된다. 예를 들어 coin[1]=2일때 j가 2부터 j-coin[i]>=0 이 성립하고 memo[j]=memo[j]+memo[j-coin[i]] 값은 2의 배수인 경우에만 1 값이 들어오게 된다. 여기서 보면 특이한 것이 coin[1]=2 이고 j=2면 memo[j-2=0] 의 경우를 더해주고 j=4 이면 memo[j-2=2]의 경우의 수를 더해주고 규칙이 보일 것이다. 그럼 문제의 조건으로 돌아와서 coin[2]일때를 보면 j=2 일경우부터 조건문이 성립하고 memo[2]=memo[2]+memo[2-2] 이 된다. 이 말은 1과 2를 이용해 2를 만드는 경우의 수는 1->2개(1을 2개이용) , 1->0 && 2->1(2를 1개이용) 두가지의 경우의 수가 나온다. 여기서 1->2는 i=0일때 1로 2를 만들수 있는 경우의 수(이전 경우의수,이값은 빨간색으로) 1->0 && 2->1은 1을 0개 선택하고 2를 하나 선택한 경우(파란색)이다. 이 경우의 수를 색으로 표현한다면 

memo[2]=memo[2]+memo[0] 이 된다. 여기서의 이해가 중요하다. 앞의 memo[2]는 현재의 동전이 아니라 이전의 동전으로 2를 만들수 있는 방법, memo[0]은 2라는 동전을 하나 선택해서 2라는 값을 만들었으므로 이전의 동전으로 0이라는 값을 만드는 경우의 수를 더하는 것이다. 그러면 더 나아가서 memo[6]=memo[6]+memo[4] 라는 값을 보자 앞의 memo[6]은 이전까지의 동전들로 6을 만드는 경우이다. 즉, 1 1 1 1 1 1, 그리고 나머지 경우를 보게되면 1 1 1 1 2, 1 1 2 2, 2 2 2 라는 경우가 남아있다. 여기서 맨위 2를 빼면 1 1 1 1, 1 1 2, 2 2라는 경우는 어느 경우인가? 2까지의 동전을 사용해 memo[4]를 만든 경우가 된다. 이런식으로 마지막 동전까지 반복을 하게 된다.