BOJ) 동전 2

동전 2

2294번: 동전 2

풀이

 

방금 전 포스팅한 LIC 문제보다 푸는데 조금 더 많은 시간이 걸렸다.

먼저, 동전 1과 다르게 k원을 만드는 최소 값을 구해야 한다는 조건이 까다롭게 느껴졌다.

또한, 만들 수 없는 경우 -1을 리턴해야한다는 부분을 간과했다.

마지막으로 고민한 부분은 점화식을 어떻게 세우는가였다.

 

우선 coin의 값이 뒤죽박죽일 수 있기 때문에, Arrays.sort를 통해 오름차순 정렬을 해주었다.

이후, 답이 될 dp[k]는 -1로 초기화 해줬다.

순차적으로 coin을 돌면서, 해당 코인이 만들어야하는 돈 k 보다 크다면 탐색을 종료해줬다. (이후에도 더 큰수만 존재)

 

for문을 통해 돈을 만들 수 있는 경우 1원 부터 탐색하면서, 어떠한 동전을 이용해서 그 금액을 만들 수 있는 경우에면 Math.min을 통해 최소값을 구했다. ( 만약 5, 6 7원이 있다면,  1~4원은 만들 수 없기 때문)

어떤 동전의 조합으로라도 i 원을 구할 수 있는 경우에는 i+coin에 최소값을 저장했다.

이 때, Math.min은 말그대로 최소값이므로, i+coin이 0인 경우 (그 전에 동전들 가지고는 만들 수 없는 경우), k원에 들어있는 -1인 경우를 회피하기 위해서 if문을 통해 저장해줬다.

 

코드

 

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

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

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

        br.close();
        solution(k,coinArr);
    }

    private static void solution(int k, int[] coinArr) {
        int[] dp = new int[k+1];
        dp[k] = -1;
        Arrays.sort(coinArr);
        for(int coin : coinArr) {
            if(coin >k) { break; }
            dp[coin] =1;
            for(int i=1; i+coin<=k; i++) {
                if(dp[i] >0) {
                    dp[i + coin] = Math.min(dp[i + coin], dp[i] + 1);
                    if (dp[i + coin] <= 0) dp[i + coin] = dp[i] + 1;
                }
            }
        }
        System.out.println(dp[k]);
    }
}