[BOJ] 백준 2293번 동전1 (Java)

#2293 동전1

난이도 : 실버 1

유형 : DP

2293번: 동전 1

▸ 문제

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

주어진 동전으로 k원이 될 수 있는 모든 경우의 수를 출력하는 문제이다. 해당 문제는 Bottom-up방식으로 주어진 n개의 동전으로 차례대로 경우의 수를 구하여 dp에 저장하는 식으로 접근하였다.

 

dp는 1차원 배열로 주어진 동전(0~i)으로 i원을 만들 수 있는 경우의 수를 저장한다.

• dp[i] = coin[0~i]로 i원으로 만들 수 있는 경우의수

 

시뮬레이션

1. 주어진 코인 n개를 순차적으로 탐색해준다. i : 0~n-1 
2. 현재의 동전(coin[i])가 j보다 작거나 같으면 해당 (j-coin[i])의 경우를 더해준다. j : 1~k 

idx	0	1	2	3	4	5	6	7	8	9	10
coin[0] = 1	1	1	1	1	1	1	1	1	1	1	1
coin[1] =2	1	1	2	2	3	3	4	4	5	5	6
coin[2] =5	1	1	2	2	3	4	5	6	7	8	10

 

풀이 코드 

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

public class Main {

	public static void main(String[] args) throws IOException{
		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];
		for(int i=0; i<n; i++) {
			coin[i] = Integer.parseInt(br.readLine());
		}
		
		int[] dp = new int[k+1];
		dp[0] = 1;
		for(int i=0; i<n; i++) {
			int v = coin[i];
			for(int j=1; j<k+1; j++) {
				if(j>=v) {
					dp[j] += dp[j-v];
				}
			}
		}
		System.out.println(dp[k]);
	}
}