[백준] 동전 9084 - JAVA

문제

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

전략

• 동전으로 가능한 금액의 가짓수를 구하기 때문에 처음에 떠올린것은 완전탐색, 그리디 , DP
• 이 중 테스트 케이스가 10 , 동전의 가짓수가 20 , 금액은 10000이다.
  • 완전탐색 : 동전의 종류별로 조합을 통해 금액 확인 ⇒ 시간복잡도가 20! * 10으로 너무 크다
  • 그리디 : 값이 큰 동전을 먼저 사용하는 방식은 최적해를 보장하지 않는다.
  • 시간복잡도까지 고려해서 DP로 접근하는것이 맞다고 생각해 고민하였다.
• dp배열을 금액에 따른 가짓수로 두었을때 2중 for문으로 동전별로 가능한 금액의 가짓수를 세는것
  • dp[j] += dp[j - coin] (단, j - coin >= 0일 때)
• 하지만 dp배열이 1차원일 경우 5+7과 7+5처럼 중복으로 가짓수를 계산할 수 있다는것을 깨닫고
• knapsack처럼 동전의 상태를 별도로 저장하는 2차원 배열을 선택해야한다고 생각해 문제를 풀었다.

코드

package acmicpc;

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

public class Back9084_동전 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();
    static int N, T, target;
    static int[] coins;
    // coin종류가 정렬되서 나옴 -> 작은거 부터 먼저 세야 전체 가짓수를 반영할 수 있음
    static int[][] dp; // [반영된 동전들 중 최대 인덱스][금액] = 가짓수
    // (5 , 7로 60만들기 5가 12개 (5+7)이 5개) -> 따라서 동전 종류 별도로 저장해야함
    //dp 배열이 1차원일 경우 5+7과 7+5처럼 중복 계산이 나올 수 있음
    // knapsack처럼 작은 동전부터 가능한 금액에 + 다음 동전의 금액

    public static void main(String[] args) throws IOException {
        tokens = new StringTokenizer(br.readLine());
        T = Integer.parseInt(tokens.nextToken());
        for (int t = 0; t < T; t++) {
            N = Integer.parseInt(br.readLine());
            coins = new int[N + 1];
            tokens = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                coins[i] = Integer.parseInt(tokens.nextToken());
            }
            target = Integer.parseInt(br.readLine());
            dp = new int[N + 1][target + 1];
            for(int i = 1; i < coins.length;i++){
                dp[i][0] = 1;
            }
            // ex) 3을 1과 2로 만들때 1,1,1 과 1,2 2가지 경우의 수중
            for (int i = 1; i < dp.length; i++) {
                for (int j = 1; j <= target; j++) {
                    dp[i][j] = dp[i - 1][j]; // 이부분을 통해 1,1,1은 이미 coin[1]을 통해 이미 가짓수가 반영됨
                    if (j - coins[i] >= 0 && dp[i][j - coins[i]] > 0) {
                        dp[i][j] +=  dp[i][j - coins[i]] ; // 따라서 2가 반영되기전 가능한 가짓수 dp[i][1]를 더해주면 됨.

                    }
                }
            }
            System.out.println(dp[N][target]);
//            for (int[] arr : dp) {
//                System.out.println(Arrays.toString(arr));
//            }
        }

    }

}

유의사항

• dp[i][0]을 1로 모두 초기화 하자
• dp[i][j-coins[i]]는 이미 dp[i-1][j-coins[i]]의 상태값을 반영했다