[PS] 인프런 강의 - DP 5. 동전교환(냅색 알고리즘)

 

문제

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

▣ 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=50)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다. 각 동전의 종류는 100원을 넘지 않는다.

▣ 출력설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

▣ 입력예제 1
3
1 2 5
15

▣ 출력예제 1
3

출력설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

풀이

 

주석

 

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

       Scanner in = new Scanner(System.in);
       
       int n = in.nextInt(); //동전의 종류 개수 1~50
       int coin[] = new int[n];
       
       for(int i=0; i<n; i++) {
    	   coin[i] = in.nextInt(); //동전 종류(무한정 쓸 수 있다, 100원을 넘지X)
       }
       
       int m = in.nextInt();//거슬러 줄 금액 1~500
       
       int dy[] = new int[m+1];//j원일 때 거슬러 줄 동전의 최소개수 (idx가 금액과 같도록)
       
       Arrays.fill(dy, Integer.MAX_VALUE); //큰 값으로 초기화 -> 이 값보다 작을 때 바꾸기 위해
       dy[0] = 0;
       
       for(int i=0; i<n; i++) { //동전 종류 순회
    	   for(int j=coin[i]; j<=m; j++) { //dy[코인의 금액]부터 거슬러 줄 금액까지 순회
    		   //j원에 i코인 1개 추가. ex) j=9, i코인 값=5 : 9원-5원= dy[4] + 1개 해준다
    		   dy[j] = Math.min(dy[j], dy[j - coin[i]] + 1);  //원래 dy값 보다 작으면 바꾼다.
    	   }
       }
       
       System.out.println(dy[m]);

    }
}