백준 2293번

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

2293번: 동전 1

 

풀이

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

public class Main {
    private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static final StringBuilder stringBuilder = new StringBuilder();

    public static void main(String[] args) throws Exception {
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());
        int k = Integer.parseInt(stringTokenizer.nextToken());

        int[] currentArr = new int[k + 1];
        int[] nextArr = new int[k + 1];
        int[] coin = new int[n];

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

        for (int i = 1; i < k + 1; i++) {
            if (i % coin[0] == 0) {
                currentArr[i] = 1;
            }
        }

        for (int i = 1; i < n; i++) {
            int coinValue = coin[i];

            for (int j = 1; j < k + 1; j++) {
                if (j < coinValue) {
                    nextArr[j] = currentArr[j];
                } else if (j == coinValue) {
                    nextArr[j] = currentArr[j] + 1;
                } else {
                    nextArr[j] = currentArr[j] + nextArr[j - coinValue];
                }
            }

            currentArr = nextArr;
        }

        System.out.println(stringBuilder.append(currentArr[k]));
    }
}