[백준]2293번. 동전1(JAVA)

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

---

풀이

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

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

        int[] arr = new int[n + 1];
        int[] dp = new int[k + 1];
        dp[0] = 1;

        for(int i = 1 ; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            for (int j = arr[i]; j <= k; j++)
                dp[j] += dp[j - arr[i]];
        }

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

}

 

dp를 이용해 부분적으로 해결해나가는 문제이다.

문제 풀이에 대해 생각해보면

처음에 1원 동전으로 구할 수 있는 것을 모두 구한다.

그 다음에 7원을 만든다고 생각해보자. 1원으로 만들 수 있는 방법에다가 2원짜리를 뺀 5원을 만드는 방법을 구해서 더하면 된다. 또한 이 5원을 만드는 방법 역시 이 전에 1원으로만 만드는 방법 + 2원으로 만드는 방법 + 5원으로 만드는 방법이 계속해서 추가되는 방식인 것이다.

이해가 잘 안 된다면 코드에 직접 값을 넣고 손으로 하나씩 따라가보면서 점화식을 본인의 것으로 만드는 것이 중요하다고 생각한다.