백준 - 2293번

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

2293번: 동전 1

 

문제 풀이

Dynamic Programming으로 접근한다.

첫 번째 동전만 사용하여 각 k값 마다 가능한 경우의 수를 찾는다.

첫 번째~두 번째 동전만 사용하였을 때, 각k 값 마다 가능한 경우의 수를 찾는다.이 때, 첫 번째 동전만 사용해서 구했던 경우의 수를 활용한다.

첫 번째~n 번째 동전을 사용하였을 때까지 반복한다

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
 
        int n = in.nextInt();
        int s = in.nextInt();
        
        int[] coin = new int[n];
        int[] dp = new int[s+1];
        
        for(int i = 0 ; i < n ; i++) {
            coin[i] = in.nextInt();
        }
        
        dp[0] = 1; //최초 시작점
        for(int i = 0 ; i < n ; i++) {
            for(int j = 1 ; j <= s ; j++) {
                if(j - coin[i] >= 0) dp[j] += dp[j - coin[i]];
            }
        }
        System.out.println(dp[s]);
    }
}