백준 2293 동전 1 (Java)

Problem

• 문제 링크

동전의 갯수와 가치가 주어졌을 때 동전의 합이 K 를 이루는 모든 경우의 수를 구하는 문제입니다.

Solution

dp 문제입니다.

dp[i] 는 i 원까지 동전의 경우의 수 입니다.

dp[j] += dp[j - coin[i]]; 식은 j 원이 되기 위해서 추가되는 동전의 수라고 생각하며 됩니다.

예를 들어 j 가 10 이고 동전 1, 2, 5 를 갖고 있을 때 경우의 수는

1. dp[9] + 1 원
2. dp[8] + 2 원
3. dp[5] + 5 원

이렇게 세가지 경우의 수가 됩니다.

dp[9], d[8], dp[5] 또한 각각 해당 인덱스까지의 모든 경우의 수 이기 때문에 전부 더해주면

dp[10] 의 총 경우의 수가 됩니다.

Java Code

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

class Main {	
	public static void main(String args[]) throws Exception {
		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[] 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 = coin[i]; j <= k; j++) { 
				dp[j] += dp[j - coin[i]];
			}
		}
		
		System.out.println(dp[k]);
	}
}