b.2293 동전 1

 

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

 

고민의 흔적

 

 

이 문제는 dp를 활용하여 N가짓 수의 동전이 주어졌을때

K의 값을 몇가지 방법으로 나타낼 수 있는지 즉 몇가지 조합으로

K값을 나타낼 수 있는지에 대한 경우의수를 묻는 문제다.

 

k가 3이면 2,1 과 1,2 가 있는데 이는 순서만 다르기에 같은경우의 수로 취급한다.

 

이문제를 보자 2차원 DP 배열을 생각해 낼 수 있었다.

dp [i][j] 는 i까지 동전을 사용했을 때 나타낼 수 있는 경우의 수로 정의하고

dp[0][j]에서 0은 coins[0]이므로 0까지의 동전이아니라 coins[0] 동전만 사용했을때

경우의 수가 된다.

 

이를 통해 점화식을 세워 봤을 때, 

 

dp[i][j] = dp[i-1][j];
if (j >= coins[i]) {
    dp[i][j] += dp[i][j - coins[i]];
}

다음과 같은 점화식을 세워볼 수 있었다.

 

 

 

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

public class b2293 {

    static int N, K;
    static int[][] dp;
    static int[] coins;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        coins = new int[N];

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

        Arrays.sort(coins);
        logic();
        System.out.println(dp[N-1][K]);
    }

    private static void logic() {
        dp = new int[N][K+1];

        for (int i = 0; i <= K; i++) {
            dp[0][i] = (i % coins[0] == 0) ? 1 : 0;
        }

        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= coins[i]) {
                    dp[i][j] += dp[i][j - coins[i]];
                }
            }
        }
    }
}