[JAVA] BOJ2293 동전 1

알고리즘 분류

• 다이나믹 프로그래밍

문제 풀이 방법

동전들의 가치를 저장하는 num 배열을 입력받습니다.
dp[i][j] 배열은 인덱스 i번째 동전까지 사용했을 때, 가치 j를 만들 수 있는 경우의 수라고 정의했습니다.

 

1. 동전들을 num 배열에 저정합니다.
2. 첫 번째 동전만 사용할 경우, j(가치) % num[i] == 0일 때, 해당 동전으로 가치를 만들 수 있는 것이므로 arr[i][j]의 값을 1로 만들어주었습니다.
   • e.g. 가치가 14이고, 첫 번째 동전이 7일 경우 dp[0][7]과 dp[i][14]의 값만 1이고, 나머지 값은 0의 값을 가짐
3. 동전을 두 개 이상 사용하는 경우는 dp배열은 다음과 같습니다.
   • dp[i][j] = dp[i - 1][j] + dp[i][j - arr[i]]
   • 이 때, j - arr[i] >= 0일 경우, dp[i][j]에 dp[i][j - arr[i]] 값을 더해줍니다.
     • 점화식이 이해가 잘 되지 않을 수도 있는데, dp[2][5]의 경우와 dp[2][10]의 경우를 생각하면 쉽게 생각할 수 있습니다.

 

코드

/*
동전 1
 */

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

public class BOJ2293 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n, k, arr[], dp[][];

    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());

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

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

        dp = new int[n][k + 1];
        for(int j = 1; j < n; j++) dp[j][0] = 1;

        for(int i = 0; i < n; i++) {
            for(int j = 1; j < k + 1; j++) {
                if(i == 0) if(j % arr[i] == 0) dp[i][j] = 1;
                if(i > 0) {
                    dp[i][j] = dp[i - 1][j];
                    if(j - arr[i] >= 0) dp[i][j] = dp[i - 1][j] + dp[i][j - arr[i]];
                }
            }
        }

        System.out.println(dp[n - 1][k]);
    }
}

 

느낀점

처음 점화식을 생각할 때, 어떻게 정의해야될지 감이 안와서 어려웠던 것 같습니다. 그래도 하나씩 차근 차근 생각해서 문제를 풀 수 있었습니다.
그리고 다른 사람의 코드를 봤을 때, 제 코드보다 간결하게 문제를 푼 사람들이 많았습니다. 다른 사람들의 코드를 이해하면서, 다른 방법으로 어떻게 풀 수 있는지 고민해봐야겠습니다!