[백준] 9084: 동전 JAVA

접근

처음엔 기존 냅색 알고리즘(평범한 배낭 문제)처럼 이차원 dp 배열을 선언했었다. dp[i][j] = i번째 동전까지 써서 j원을 만들 수 있는 경우의 수로 정의하고. 그런데 문제를 다시 생각해보니, 서로 다른 물건을 담는 것과는 다르게 이 문제에서는 같은 금액의 동전을 여러 번 써도 된다는 점을 깨달았다. 그래서 for(int i = 0;i < m;i += coin) 과 같이 n개의 동전에 대해서 모두 1을 설정한 후 시작해야 하나? 싶었다. 근데 그러면 배열에 0이 너무 많고 비효율적인 것 같아서 접근이 잘못된 것 같았다. 

 

그래서 사실 솔루션을 살짝 참고했다.. 역시나 이차원이나 쓸 필요가 없었다. 2년 만에 알고리즘을 풀다보니 까먹은 내용이 너무 많았는데, 특히 dp가 감을 다시 되살리기 제일 어려운 것 같다. 앞으로는 일차원 배열을 재사용할 수 있는지 고려해볼 것! 그리고 무엇보다 dp는 직접 표를 그려가며 규칙을 찾는게 제일 쉬운 접근법인 것 같다. 머리로만 풀려고 하지 말자. 

 

코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int tc = Integer.parseInt(br.readLine());
        for(int t = 0;t < tc;t++){
            // 입력값 저장
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] coins = new int[n];
            
            for(int i = 0;i < n;i++){
                int coin = Integer.parseInt(st.nextToken());
                coins[i] = coin;
            }

            int m = Integer.parseInt(br.readLine());

            // 냅색 알고리즘 계산
            int answer = solve(coins, n, m);
            sb.append(answer).append("\n");
        }

        // 결과값 출력
        System.out.println(sb.toString());
    }

    static int solve(int[] coins, int n, int m){
        int result = 0;
        int[] dp = new int[m+1];

        for(int i = 1;i <= n;i++){
            int curCoin = coins[i-1];
            
            for(int j = 0;j <= m;j++){
                if(j == curCoin) dp[j] += 1;
                else if(curCoin < j) dp[j] += dp[j-curCoin];
            }
        }
        result = dp[m];
        return result;
    }
}