이코테 - 효율적인 화폐 구성 with JAVA

 

 

 

해결

예를 들어, 동전이 2원 3원이 존재하고 15원을 만든다고 가정하자.

 

2원만 사용하는 경우

만약, 0원이 존재한다면 0원+2원으로 2원을 만들 수 있다.

만약, 1원이 존재한다면 1원+2원으로 3원을 만들 수 있다.

만약, 2원이 존재한다면 2원+2원으로 4원을 만들 수 있다.

만약, 3원이 존재한다면 3원+2원으로 5원을 만들 수 있다.

 

이를 식으로 정리하면, dp[i] = Math.min(dp[i], dp[i-2]+1) 이 된다.

2원 = Math.min(2원, (2-2)원 +1)

3원 = Math.min(3원, (3-2)원 +1)

4원 = Math.min(4원, (4-2)원 +1)

 

 

 

 

 

코드

package JAVA.TCT.DP;

import java.util.*;

// 효율적인 화폐 구성
public class Practice4 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<Integer> coins = new ArrayList<>();
        for(int i=0; i<n; i++){
            coins.add(sc.nextInt());
        }
        int[] dp = new int[m+1];
        Arrays.fill(dp, (int)1e9);

        dp[0] = 0;
        for(int i=0; i<n; i++){
            for(int j=coins.get(i); j<m+1; j++){
                dp[j] = Math.min(dp[j], dp[j-coins.get(i)]+1);
            }
        }

        if(dp[m] >= 100000){
            System.out.println(-1);
        }
        else{
            System.out.println(dp[m]);
        }
    }
    
}