동전1 - 2293

문제

풀이

import java.util.Scanner;

// 동전 1 - G5 -> 다이나믹으로 풀어야함..
public class ex2293 {

    static int n,m;
    static int[] arr;
    static int[] dy;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        arr = new int[n+1];
        dy = new int[m+1];
        dy[0]=1; //여기에 1을 선언 해줘야 1원으로 1을 구하는 경우에 1이 들어감.

        for(int i=1; i<=n; i++){
            arr[i]=sc.nextInt();
        }

        for(int i=1; i<=n; i++){
            for(int j=arr[i]; j<=m; j++){
                dy[j]+=dy[j-arr[i]];
            }
        }
        System.out.println(dy[m]);
    }
}

dy[0]=1을 해줘야한다. 0원을 만드는법 1가지.
동전의 종류별로 dy[j]=dy[j-arr[i]]를 해준다. 그러면 해당 동전의 경우와 다른 동전으로 만들수있는 경우의 수가 중첩되면서 증가한다. 어렵다,,

다이나믹 프로그래밍 문제 많이 풀어보자.