[백준] 6126 Cow Cash - Java

 

 

 

문제 출저

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

 

 

 

 

문제 풀이

동전의 종류와 금액이 주어집니다. 주어진 동전으로 금액을 만들 경우의 수를 구해야 합니다. 

dp를 이용해 문제를 풀었습니다. int[] dp = new int[n+1] 로 선언하여 금액 만큼 길이를 만듭니다.

 for (int j = coin; j <= n; j++) {
    dp[j] = dp[j] + dp[j-coin];
}

점화식을 세워서 문제를 풀었습니다. 

 

 

 

소스 코드

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

/*
Cow Cash
https://www.acmicpc.net/problem/6126

50% 틀렸습니다.
-> dp 자료형을 long으로 바꾸어 해결했다.
 */

public class Main {

    static int v, n;
    static long[] dp;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        dp = new long[n+1];
        dp[0] = 1;

        for (int i = 0; i < v; i++) {
            int coin = Integer.parseInt(br.readLine());

            if (coin > n) continue;

            for (int j = coin; j <= n; j++) {
                dp[j] = dp[j] + dp[j-coin];
            }
        }

        System.out.println(dp[n]);

    }

}