[백준-2293번 자바/java] 동전 1 _디버깅의 눈물

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

2293번: 동전 1

 

 

 

동전 1 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

4 MB

46052

20963

15808

45.652%

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

예제 입력 1 복사

3 10
1
2
5

예제 출력 1 복사

10

 

 

 

 

 

---

 

 

 

 

 

 

체크 포인트

 

1. 다이나믹 프로그래밍(Dynamic Programming, 동적계획법) 이용

-큰 문제를 작은 경우부터 탐색해 추론해나가는 dp를 이용해 풀이를 시도했다.

-문제의 조건 중 '사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.'라는 부분 때문에 까다로웠다. 예를 들어 동전의 합 3을 만들 때를 살펴 보면,

 

(1,1,1), (1,2), (2,1) 총 3가지가 나오지만, '사용한 동전의 구성이 같고 순서만 다른 것은 같은 경우'라는 조건을 적용하면 (1,1,1),(1,2)로 총 2가지가 되는 것이다.

 

 

-이어서 예제 1을 예시로, 1원, 2원, 5원의 동전으로 총 10원을 만드는 경우의 수를 추론해보자.

-동전의 종류는 static int[] coin이라는 배열에 담았다. coin[0]=1원, coin[1]=2원, coin[2]=5원이다.

 

(1)가장 작은 단위인 1원 동전으로 1원에서부터 10원을 만드는 경우의 수를 구해보자.

 

 

-1원으로 1원에서 10원을 만들 수 있는 경우의 수

 

총합(k)	1	2	3	4	5	6	7	8	9	10
coin[0] 1원	1	1	1	1	1	1	1	1	1	1

 

 

(2)다음으로 1원,2원 동전으로 1원에서부터 10원을 만드는 경우의 수를 추가하면 다음과 같다.

 

총합(k)	1	2	3	4	5	6	7	8	9	10
coin[0] 1원	1	1	1	1	1	1	1	1	1	1
coin[1] 1원,2원	1	2(1+1)	2(1+1)	3(1+2)	3(1+2)	4(1+3)	4(1+3)	5(1+4)	5(1+4)	6(1+5)

 

-k(동전의 총합)가 1인 경우, 2원짜리 동전으로 동전의 총합 1원을 만들 수 없다. 즉, k=1일 때, coin[0] = coin[1] = 1이다.

그래서 k>=coin[1]일 때부터 동전을 만드는 경우의 수가 달라진다.

 

-coin[1]에서 k가 3원인 경우는,

 

1원짜리 동전만으로 3원(k=3)을 만드는 경우의 수 1 + 1원,2원 동전으로 1원(k=1)을 만드는 경우의 수 1

= 

2(1+1)

 

로 표현할 수 있다. 1원,2원 동전으로 1원을 만드는 경우에서 2원을 더하면 3원이 되기 때문이다.

-coin[1]에서 k가 4원인 경우는,

 

1원짜리 동전만으로 4원(k=4)를 만드는 경우의 수 1 + 1원,2원 동전으로 2원(k=2)을 만드는 경우의 수 2

=

3(1+2)

 

로 표현할 수 있다. 위의 설명을 좀 더 일반화 하면 아래와 같이 표현할 수 있다.

 

 

k>=coin[i]일 때, dp[k] = dp[k] + dp[k-coin[i]]

 

 

 

총합(k)	1	2	3	4	5	6	7	8	9	10
coin[0] 1원	1	1	1	1	1	1	1	1	1	1
coin[1] 1원,2원	1	2	2	3	3	4	4	5	5	6
coin[2] 1원,2원,5원	1	2	2	3	4(3+1)	5(4+1)	6(4+2)	7(5+2)	8(5+3)	10(6+4)

 

-마찬가지로 1원, 2원, 5원을 모두 사용해서 10원을 나타내는 경우의 수는 위와 같다. k가 5가 되기 전까지는 동전 구성에 5원이 사용될 수 없기 때문에, k=1,2,3,4인 경우, 이전에 구했던 경우의 수와 동일하다.

 

 

 

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public  class Main {
	
	// 동전의 합으로 k원을 만들 수 있는 경우의수를 담는 배열
	static int[] dp;
	// 동전의 종류 n
	static int n;
	// 동전의 종류를 담아주는 배열 
	static int[] coins;
	
    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
    	int k = Integer.parseInt(st.nextToken());
    	
    	// 동전 배열 초기화
    	coins = new int[n];
    	
    	// 동전 종류 입력. 예제1 기준 1,2,5
    	for(int i=0; i<n; i++){
    		coins[i] = Integer.parseInt(br.readLine());
    	}
    	
    	// 동전합이 k가 되는 경우의 수를 담는 배열 초기화
    	dp = new int[k+1];
    	// 경우의 수 연산을 위한 dp[0]값=1로 초기화
    	dp[0] = 1;
    	
    	// 탐색 시작
    	solution(k);
    	
    	
    	
    	
    } // end of Main
    
    
    static void solution(int k) {
    	
    	// n개의 동전을 작은 숫자부터 탐색하여,
    	for(int i=0; i<n; i++){
    		// 동전의 총합이 1원부터 k원이 될때까지 탐색
    		for(int j=1; j<=k; j++){
    			// 동전의 총합 기준이 해당 동전의 종류보다 커지면,
    			if(coins[i]<=j){
    				// 새로운 dp[j] = 이전의 dp[j] + dp[j-동전의 종류]
    				dp[j] = dp[j] + dp[j-coins[i]];
    				//System.out.println("dp[j] : " + dp[j]);
    			}
    		}
    	}

    	// 정답 출력
    	System.out.println(dp[k]);
    	
    } // end of solution
    
} // end of Main