[백준 2293] 동전 1 (자바)

백준 2293번 동전 1 (자바)

 

 

 

출처

www.acmicpc.net/problem/2293

2293번: 동전 1

 

 

 

문제

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

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

입출력 예

입출력 예 1

 

 

 

접근 방법

문제의 조건을 이해해보면 자신의 상, 하, 좌, 우에 있는 스티커는 사용할 수 없다.

동전을 어떻게 사용해서 점화식을 세울까 고민을 많이 했지만 결국 생각해내지 못했다.

설명이 잘 되어있는 블로그를 찾아보던 중 마이구미님의 블로그에서 답을 찾을 수 있었다.

mygumi.tistory.com/129

동전 교환 관련 문제 접근 :: 마이구미

위 블로그에 따르면 1원을 통해 ~ 10원까지 만들 수 있는 경우의 수를 만든 후, 3원을 통해...... + 5원을 통해 ........ 구하면 풀린다고 명시가 되어있다. 또한, 이를 통해 공식을 만들 수 있다고 한다.

dp[0] = 1; 
for (int i = 0; i < n; i++) { 
	for (int j = coin[i]; j <= k; j++) { 
		dp[j] = dp[j] + dp[j - coin[i]]; 
	} 
}

위 공식은 말 그대로 각 동전(원)으로 만들 수 있는 경우의 수를 차근차근 누적시키는 방법이다.

ex) coin[2] = 2,  4원을 구하는 경우
dp[4] = dp[4] + dp[4-2] = dp[4] + dp[2]
기존 2원을 구하는 경우에서 2원을 사용하여 구하는 경우를 더한다.
2원에서 4원은 2원을 하나 더 추가하는 방법밖에 없다.

 

 

점화식 : dp[j] = dp[j] + dp[j-coin[i]]

 

 

 

내 코드

package dynamicprogramming;

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

public class Coin1 {
	public static void main(String[] args) throws IOException {
	
		//n가지 종류의 동전
		//동전을 합해서 K원 만들기
		//경우의 수
		//동전 사용 제한 없음
		
		//순서 달라도 구성 같으면 같은 경우
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(reader.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int[] map = new int[n+1];
		
		for (int i=1; i<=n; i++) {
			map[i] = Integer.parseInt(reader.readLine());
		}
		
		//dp : 동전 i개 사용했을 때 가질 수 있는 경우의 수
		int[] dp = new int[k+1];
		
		//동전 공식 : dp[j] = dp[j] + dp[j-coin[i]]
		//coin[i]원으로 1~k까지 만들 수 있는 경우의 수를 누적해서 담는다.
		//ex) map[2] = 2, 
		//4원을 구하는 경우
		//dp[4] = dp[4] + dp[4-2] = dp[4] + dp[2]
		//기존 2원을 구하는 경우에서 2원을 사용하여 구하는 경우를 더한다.
		//2원에서 4원은 2원을 하나 더 추가하는 방법밖에 없다.
		
		dp[0] = 1;
		
		for (int i=1; i<=n; i++) {
			for (int j=map[i]; j<=k; j++) {
				dp[j] = dp[j] + dp[j - map[i]];
			}
		}
		System.out.println(dp[k]);
		
	}
}

 

 

 

고려할 점

1. 규칙을 찾아 점화식을 세울 것

2. 직접 써보며 규칙을 찾을 것