[BOJ] 백준 2624번 동전 바꿔주기 (Java)

#2624 동전 바꿔주기

난이도 : 골드 5

유형 : DP

2624번: 동전 바꿔주기

▸ 문제

명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.

• 20 = 10×2 
• 20 = 10×1 + 5×2 
• 20 = 10×1 + 5×1 + 1×5 
• 20 = 5×3 + 1×5

입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 방법 의 수는 231-1을 초과 하지 않는 것으로 가정한다.

▸ 입력

첫째 줄에는 지폐의 금액 T(0＜T ≤ 10,000), 둘째 줄에는 동전의 가지 수 k(0＜k ≤ 100), 셋째 줄부터 마지막 줄까지는 각 줄에 동전의 금액 pi(0＜pi ≤ T)와 개수 ni(0＜ni ≤ 1,000)가 주어진다. pi와 ni사이에는 빈칸이 하나씩 있다.

▸ 출력

첫째 줄에 동전 교환 방법의 가지 수를 출력한다. 방법이 없을 때는 0을 출력한다.

 

문제 풀이 

주어진 동전의 종류와 갯수로 T를 만들 수 있는 방법의 수를 구하는 문제이다. 보자마자 순열 조합이 생각났다. 해당 문제는 순서를 따지지 않고 중복을 정해진 갯수만큼 허용한다. 재귀호출 탐색으로 쉽게 구할 수 있을 것 같다

 

📚 조건

  ∙ 지폐의 금액 T (0 <= T <= 10,000)

  ∙ 동전의 가지 수 k (0 <= k <= 100)

  ∙ 동전의 금액 pi (0 <= pi <= T)

  ∙ 동전의 개수 ni (0 <= ni <= 1,000)

k가지의 수 동전을 각 ni번씩 조회하여 탐색할 것이므로 최악의 경우 100,000번 정도 걸리므로 재귀호출 탐색으로 메모리나 시간적으로 문제없다. 

int res = 0;
for(int i=0; i<coin[coinType][1]+1; i++) {
	int cost = coin[coinType][0]*i;
	res += dfs(money + cost , coinType+1 );
}
return dp[coinType][money] = res;

 

주어진 동전으로 모든 조합을 다 만들어 본 다음 지폐의 금액 T와 일치하는 경우 리턴해주면 된다.

if(money == t) {
	return 1;
}

 

재귀 탐색 풀이 코드 

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

public class Main {

	static int t,k;
	static int[][] coin;
	static int[][] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		t = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());
		coin = new int[k][2];
		
		StringTokenizer st = null;
		for(int i=0; i<k; i++) {
			st = new StringTokenizer(br.readLine());
			coin[i][0] = Integer.parseInt(st.nextToken());
			coin[i][1] = Integer.parseInt(st.nextToken());
		}
		dp = new int[k][t+1];
		for(int i=0; i<k; i++) {
			for(int j=0; j<t; j++) {
				dp[i][j] = -1;
			}
		}
		System.out.println(comb(0, 0));
	}
	
	static int comb(int money, int coinType) {
		if(money == t) {
			return 1;
		}
		if(coinType ==k || money>t) {
			return 0;
		}
		if(dp[coinType][money] !=-1) {
			return dp[coinType][money];
		}
		
		int res = 0;
		for(int i=0; i<coin[coinType][1]+1; i++) {
			int cost = coin[coinType][0]*i;
			res += comb(money + cost , coinType+1 );
		}
		return dp[coinType][money] = res;
	}


}

 

 

반복문 풀이 코드 

솔직히 이런 조합이나 순열같은 문제는 Bottom-up 반복문으로 푸는건 그리 좋아하지 않는다. 하지만 연습이니깐..! 효율성도 더 좋으니깐 한 번 코딩해봤다.

 

사실 그냥 위의 재귀호출로 풀었거나 그림이 그려졌다면 저 식을 반복문으로 다시 풀어내주면 된다. 아니면 처음부터 반복문으로 접근한다면 배낭 채우기 문제를 생각해서 풀이하면 쉬울 것 같다. 

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

public class Main {

	static int t;
	static int k;
	static int[][] coin;
	static int[][] dp;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		t = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());
		
		coin = new int[k+1][2];
		
		StringTokenizer st = null;
		for(int i=1; i<k+1; i++) {
			st = new StringTokenizer(br.readLine());
			coin[i][0] = Integer.parseInt(st.nextToken());
			coin[i][1] = Integer.parseInt(st.nextToken());
		}
		
		dp = new int[k+1][t+1];
		dp[0][0] = 1;
		for(int i=1; i<k+1; i++) {
			int cost = coin[i][0];
			for(int j=0; j<coin[i][1]+1; j++) {
				for(int k=0; k<=t; k++) {
					int pos = k + cost*j;
					if(pos>t) break;
					dp[i][pos] += dp[i-1][k];
				}
			}
		}
		System.out.println(dp[k][t]);
	}

	
}

실행 결과

재귀 풀이

반목문 풀이