본문 바로가기

Dot Algo∙ DS/PS

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

    #2293 동전1

    난이도 : 실버 1

    유형 : DP

     

    2293번: 동전 1

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

    www.acmicpc.net

    ▸ 문제

    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]);
    	}
    }