[BOJ] 2294번 동전2

개요

동전1의 발전 문제 점화식을 찾는 것이 중요

문제링크

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Baekjoon2294 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] coin = new int[n];    //동전을 저장하는 배열  
        int[] dp = new int[k+1];    //DP테이블을 저장하는 배열(동전의 합 0~k)
        for(int i=0;i<n;i++) 
            coin[i] = Integer.parseInt(br.readLine());
        Arrays.sort(coin);
        for(int i=1;i<dp.length;i++)
            dp[i] = 10001; //dp 테이블 최대값으로 초기화

        for(int i=0;i<n;i++) {
            for(int j=1;j<=k;j++) {
                if(coin[i]<=j)  {//동전의 합인 j가 i번째 동전보다 크거나 같을 때(동전의 합에 최소한 i번째 동전이 들어갈 수 있을 때)
                    dp[j] = Math.min(dp[j], dp[j-coin[i]]+1);
                }
            }
        }
        int min;
        if(dp[k] == 10001)  //최소값이 없으면 -1
            min = -1;
        else
            min = dp[k];
        bw.write(min+"");
        bw.flush();
        
    }
}

해결 과정

동전1에서 했던 것처럼 점화식을 찾아서 해결하면 풀리는 문제

문제에서 주어진 입력을 표로 그려보면 위와 같다.

동전1과 다른점이 있다면 이번엔 경우의 수가 아닌 동전의 최소갯수라는 점인데

동전1과 크게 다른점은 없다.

규칙을 찾아보면

동전1과 같이 동전의 합이 동전의 값보다 작으면 값이 바뀌지 않는다는 점

새로 찾은 경우의 수가 기존 경우의 수보다 사용하는 동전이 많으면 바뀌지 않는다는 점

동전의 값과 비례해서 +1만큼 커진다는 점

예를 들어서 [1,5]만 사용하는 경우에 동전의 합이 5일 때를 보자

이 값은 동전의 합이 0일 때의 동전의 갯수에 +1한 것과 같다.

마찬가지로 합이 6일 경우는 합의 1일 경우에 +1한 것과 같다.

그러면 다음과 같이 점화식을 세울 수 있다.

dp[ j ] = Min( dp[ j ], dp[ j - 동전의 값 ] + 1 ) (단 동전의 값이 j보다 작거나 같을 때)

이것을 코드로 표현한 것이 아래와 같다.

for(int i=0;i<n;i++) {
    for(int j=1;j<=k;j++) {
        if(coin[i]<=j)  {//동전의 합인 j가 i번째 동전보다 크거나 같을 때(동전의 합에 최소한 i번째 동전이 들어갈 수 있을 때)
            dp[j] = Math.min(dp[j], dp[j-coin[i]]+1);
        }
    }
}

결과