[JAVA]백준 2293번: 동전 1

www.acmicpc.net/problem/2293

2293번: 동전 1

1. 문제 설명

 

n 가지 종류의 동전을 적당히 사용하여 K원을 만들게 하는 경우의 수를 구하시오.

 

2. 풀이

 

2원을 사용하여 5원을 만들고자 한다면 3원까지의 합에 2원을 더해 5원을 만들 수 있다.

 

따라서 동전을 A1, A2.... An이라 하고, 만들고자 하는 가치의 합을 Y라고 한다면

 

dp [Y]=dp [Y-A1]+dp [Y-A2]+...+dp [Y-An]이다.

 

이 점화식을 이용하여

 

새로운 동전을 하나 입력받을 때마다 그 동전을 사용하여 만들 수 있는 경우의 수를 dp 배열에 더하였다.

 

 

시간 복잡도 : O(NK)

 

 

 

3. 코드

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));


        int num, sum;

        StringTokenizer st=new StringTokenizer(br.readLine());

        num=Integer.parseInt(st.nextToken());
        sum=Integer.parseInt(st.nextToken());

        int[] dp=new int[sum+1];


        dp[0]=1;

        for(int x=0;x<num;x++){

            int base=Integer.parseInt(br.readLine());

            for(int y=base;y<=sum;y++){
                dp[y]+=dp[y-base];
            }
        }


        bw.write(String.valueOf(dp[sum]));
        bw.flush();
        bw.close();
        br.close();



    }


}