백준 2293 - 동전 1

Java

2293 번 - 동전 1

문제

접근 방법

dp[k]는 k 만큼의 가치를 만들 때 가질 수 있는 경우의 수를 담은 dp 배열이다.

또한 dp[k]는 dp[k - 코인]의 경우에 수에서 해당 코인을 하나 더 사용하였을 때, 만들어 지므로 점화식은

dp[k] = dp[k] + dp[k - coin[j]]

가 된다.

단, 각 금액을 먼저 탐색 후 동전들의 경우의 수를 더하면 순서만 다르고 조합이 같은 경우가 된다.

// 금액을 먼저 탐색
for(int i = 1; i <= k; i++) {
	for(int j = 0; j < n; j++) {
		if(i >= coin[j]) {
			dp[j] = dp[j] + dp[j - coin[i]];
		}
	}
}

이 경우, 점화식은 다음과 같이 되며
dp[k] = dp[k-coin[0]] + dp[k-coin[1]] + dp[k-coin[2]] + … + dp[k-coin[n-1]]

이는 곧 순서만 다르고 조합이 같은 경우로 중복으로 카운트 된다.

하지만 동전을 기준으로,
한가지만 사용할 때의 경우의 수, 동전을 두가지 사용할 때의 경우의 수, 동전을 세가지 사용할 때의 경우의 수..동전을 n가지 사용할 때의 경우의 수
이런식으로 사용하는 동전의 가지 수를 늘려가면서 계산을 할 시
중복의 경우의 수가 발생하지 않는다.

// 금액이 아닌 동전부터 우선 탐색
for(int i = 0; i < n; i++) {
	for(int j = 1; j <= k; j++) {
		if(j >= coin[i]) {
			dp[j] = dp[j] + dp[j - coin[i]];
		}
	}
}

코드

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

public class Main {
	static int n, result, k;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());

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

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

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}