[BOJ 2293] 동전 1 - JAVA, Gold5

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

2293번: 동전 1

풀이

사용한 알고리즘 : DP

 

풀이전략

 

위의 문제에서 주어진 입력을 표로 나타내면 아래와 같다.

 

이중배열 d[i][j]는 i와 i번 째 이전에 입력된 동전들로, 수 j를 만들 수 있는 경우의 수를 저장한다.

 

d[i][0]은 공집합인 상태로, 공집합 또한 하나의 경우의 수를 가지므로 1을 가진다.

d[0][j]은 d[i][j]의 규칙성을 찾아낸 식에서

d[i-1][j]의 i-1에서 IndexOutOfBoundsException이 발생하지 않도록 추가해준 행이다.

 

 

제출코드

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

public class Main {
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int coin[] = new int[n];
        int d[][] = new int[n+1][k+1];

        for(int i=0;i<n;++i){
            coin[i]=Integer.parseInt(br.readLine());
        }

        for(int i=0;i<=k;++i){
            d[0][i]=0;
        }

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

        bw.write(d[n][k]+"\n");
        bw.flush();
        bw.close();
    }
}