[java 백준] 골드 5/ 9084번 동전

https://www.acmicpc.net/problem/9084

9084번: 동전

import java.util.Scanner;
 
public class Main {
 
    public static int T;
    public static int N;
    public static int M;
    public static int dp[];
 
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        T=sc.nextInt();
        for(int i=0;i<T;i++) {
            N=sc.nextInt();
            int coin[]=new int[N];
            for(int j=0;j<N;j++){
                coin[j]=sc.nextInt();
            }
 
            M=sc.nextInt();
            dp=new int[M+1];
            dp[0]=1;
            for(int j=0;j<N;j++){
                for(int k=coin[j];k<=M;k++){
                    dp[k]+=dp[k-coin[j]];
                }
            }
 
            System.out.println(dp[M]);
 
        }
 
 
    }
}
 

 

이 문제는 냅색문제를 풀듯이 진행하면 된다.

냅색문제란  i번째 물건을 넣었을 때와 넣지 않았을 때, 둘 중 더 가치가 큰 것을 가져오면 된다!

아래 글이 동적계획법과 냅색문제를 잘 설명해서 첨부한다.

 

https://chanhuiseok.github.io/posts/improve-6/

[알고리즘 트레이닝] 5장 - 동적계획법과 냅색(Knapsack) (백준 12865번 평범한 배낭 문제로 살펴보기)

예를 들어 입력값이

2

1 2

1000

이라고 하자.

여기서 중요한 것은 dp[k-coin[j]] 는 j번째 동전을 넣었다는 가정하에 진행되는것

coin[0]=1 일거고 coin[1]=2일것이다. 기존의 냅색문제랑 다른 점은 반드시 동전을 넣어야 한다. 왜냐면 동전 n개를 가지고 금액 m을 넣어야 하기 때문이다. 그래서 dp[k-coin[j]]가 굉장히 중요한 코드가 된다. 

 

dp[0]은 무조건 1로 고정해준다. 

우선 j가 0일 때는 coin[0]이고 이때 금액은 1이다. 1을 가지고 특정 금액을 만드는 방법은 다 1가지 일 것이다. 

이제 j가 1일 때를 보면 coin[1]이고 이때 해당하는 금액은 2원이다!

 

dp[2]부터 차이가 생기는데 dp[2]+=dp[2-coin[1]] 이기에 dp[2]+=dp[0]이니까 dp[2]는 최종적으로 2가 된다.

사실 동전 2개 가지고 dp[2]를 만드는 방법은

1원짜리 2개 2원짜리 1개로 총 2가지이다. 이걸 누적합으로 표현하면 위의 문장과 같다. 

 

dp[3]또한 dp[3]+=dp[3-coin[1]]  dp[3]+=dp[1] 이니까 dp[3]=2이 된다.

1원짜리 3개

2원 짜리 1개 + 1원짜리 1개