[BOJ] 백준 [2293] 동전 1 JAVA

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

2293번: 동전 1

문제

풀이

동전의 배열을 coins[] 라고 하고 , 만들고 있는 갯수의 합의 결과를 dp[] 라고 하면

 

dp[k] 를 만들기위해 이전의 결과값을 더해줘야 한다.

 

기준을 conis[] 로 해서 반복문을 돌리면 coins[1] 일때 1~k원 까지 모두 체크 , coins[2] 일때 1~k원 가지 모두 체크 ..

이런식으로 해서 coins[n] 일때 모두 체크해서 기존의 dp 배열에 계속해서 추가해주면 된다.

 

점화식은 다음과 같다 => dp[i] +=dp[i-coin];

 

 

import java.util.*;
import java.io.*;
 
public class Main{
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);
        int[] coins = new int[n];
        int[] dp = new int[k+1];
        for(int i=0;i<n;i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }
        dp[0]=1;
        for (int coin : coins) {
            for(int i=1;i<=k;i++)
                if(i-coin >= 0)
                    dp[i] +=dp[i-coin];
        }
 
        System.out.println(dp[k]);
    }
}