[백준 코딩테스트] 2293번 동전1

풀이

이 문제도 동적계획법을 사용해 접근해야 한다.
먼저 점화식을 만들어야 이 문제를 풀 수 있다.
입력받은 n 크기만큼의 coin 배열과 k+1 크기 만큼의 dp 배열을 만들어준다.

이와 같이 각각 동전의 가치를 이용해 dp의 값을 갱신해준다.
이와 같이 도출한 점화식이 dp[j] = dp[j] + dp[j-coin[i]] 이다.

처음에 동전의 가치가 1일 때는 각각의 j 가치 만큼 만들 수 있는 경우의 수가 1가지 뿐이기 때문에 dp 배열의 값들은 모두 1로 초기화된다.
값이 갱신되는 경우는 j가 동전의 가치보다 크거나 같을 때 갱신된다. 해당 동전을 사용해 만들 수 있는 경우의 수가 생기기 때문이다.
그 후 동전의 가치가 2, 5 일 때 만들 수 있는 경우의 수를 모두 구해 우리가 구하려는 가치 k원의 경우의 수를 구한다.

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int answer=0;
    static int n, k;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        int[] coin = new int[n];
        int[] dp = new int[k+1];

        for(int i=0; i<n; i++){
            coin[i] = Integer.parseInt(br.readLine());
        }

        dp[0]=1;

        for(int i=0; i<n; i++){
            for(int j=1; j<=k; j++){
                if(j>=coin[i]){
                    dp[j] += dp[j-coin[i]];
                }
            }
        }

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

    }

}