코드트리 [자바 java] 동전 거슬러주기

https://www.codetree.ai/missions/2/problems/coin-change?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

거슬러줄 금액과 동전의 종류가 나오면, 거슬러줄 수 있는 최소한의 동전 수를 출력하는 문제이다.

이 문제는 dp를 사용했다.

0부터 해당 금액까지의 dp배열을 선언하고, 사용할 수 있는 동전들을 하나 쓰는 방법을 모두 비교하여 최솟값을 넣도록 하였다.

 

import java.util.*;
import java.io.*;
import java.math.*;

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 m = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());


        for(int i = 0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[m+1];

        for(int i = 1;i<=m;i++){
            int min = i;
            int ok = 0;

            for(int j = 0;j<n;j++){
                if((i - arr[j] > 0 && dp[i-arr[j]]!= 0) || i-arr[j] == 0){
                    ok = 1;
                    min = Math.min(min, dp[i-arr[j]]);
                }
            }

            if(ok == 1) dp[i] = min + 1;
            else dp[i] = 0;
            //System.out.println(dp[i]);
        }

        if(dp[m] != 0 )System.out.println(dp[m]);
        else System.out.println(-1);

        
    }
}