[BOJ 2293] 동전1

[BOJ 2293] 동전1

 

1. 문제 : Link

동전 종류 n

만들어야하는 값 k

를 받아서 k를 만족시키는 동전의 합 경우의 수를 구하는 문제

 

2. 풀이

동적 계획법을 활용하는 문제

배열에 계산된 값을 넣어주는 것을 반복한다.

 

쉽게 말하면,

1,2,5로 7이라는 숫자를 만드는 경우의 수는 7이 되기위한 모든 경우의 수들이 더해진 결과이기 때문에 동적 계획법이 사용된 것이라 할 수 있다.

https://pacific-ocean.tistory.com/200

 

3. 코드

package baekjoon;

import java.io.IOException;
import java.util.*;

public class Main {
    static int N;
    static int sum;
    static int[] coins;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        sum = sc.nextInt();

        coins = new int[N];

        for(int i=0; i<N; i++){
            coins[i] = sc.nextInt();
        }

        dp = new int[sum+1];
        dp[0] = 1;

        for(int i = 0; i < N; i++) {
            for(int j = coins[i]; j <= sum; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }

        System.out.println(dp[sum]);

    }
}