백준 2293번 ) 동전 1 (java)

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

2293번: 동전 1

 

문제

 

풀이

https://lotuslee.tistory.com/113?category=848933 

[백준 2293번] 동전 1 (java)

위 블로그를 참고했다.

dp 는 점화식 세우는게 너무 어렵다 ㅠㅠ

 

코드

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

public class BOJ_2293 {
    static int n, k;
    static int[] coin, dp;

    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());

        coin = new int[n];
        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=coin[i]; j<= k; j++) {
                dp[j] += dp[j-coin[i]];
            }
        }

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

 

 

생각 할 점

dp 문제 점화식 세우는 방법 연습하기

중복일 경우 처리하는 방법