[백준/Java] 2293번 동전1

문제 분석

해당 문제의 시간 복잡도는 0.5초이고, 메모리 제한은 4MB이다. 메모리가 굉장히 적으므로 주어진 n 크기로 2차원 배열을 만들 경우, 메모리가 초과된다. 즉, 최대 공간 복잡도가 n을 사용할 경우 사용할 수 있는 자료구조는 일차원 배열 정도이다. 1차원 배열이라는 제한에서 사용할 수 있는 알고리즘 수는 많지 않다. 이와 같은 상황을 고려하여, DP를 통해 문제를 해결해야 겠다고 생각했다.

 

문제 풀이

DP는 이전에 구했던 답을 이용하여 현재의 답을 도출하는 알고리즘이다. 그렇다면, 우리가 구해야 할 경우의 수를 이전 값을 통해 현재 값을 도출하는 형태로 구현할려면 어떤 값을 기준으로 DP를 구성해야할까. 

해당 문제는 동전의 합이 k가 되도록 하는 경우의 수이다. k값에 따라 동전의 경우를 구해야 하므로, 동전의 합을 DP의 인덱스로 설정하고 DP의 값은 해당 경우의 수로 설정한다. 동전의 합은 어떤 동전을 사용할 수 있는지에 따라 달라진다. 즉, 사용할 수 있는 동전의 개수가 늘어나면, 경우의 수도 증가한다는 것이다. 이런 메커니즘에서 이전 값을 통해 현재 값을 구한다고 생각하자.

위의 그림은 1만 사용할 때, 1과 2를 사용할 때, 1과 2와 3의 경우를 사용할 때의 경우를 분리해서 기록한 것이다. 이때 우리는 동전이 추가될 때마다 가능한 경우가 증가될 수 있다는 것을 알고있다. 따라서 합이 k인 경우의 수는 동전이 추가되지 전의 경우와 해당 k값에서 추가된 코인의 값만큼 빼준 경우의 수를 더하면, k값에 해당하는 경우를 구할 수 있다.

이를 식으로 표현하면, dp[k] = dp[k] + dp[k-coin[i]] 이다.

 

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

public class Main {

    static int n, k;
    static int[] dp;
    static int[] coins;

    public static void main(String[] args) throws IOException {
        input();
        setDp();
        output();
    }

    public static void input() 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());
        dp = new int[k + 1];
        coins = new int[n];

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

    public static void setDp() {
        dp[0] = 1;

        for (int i = 0; i < n; i++) {
            for (int j = coins[i]; j <= k; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
    }

    public static void output() {
        System.out.println(dp[k]);
    }
}