[Java] 카지노 교환원

1. 문제

당신은 카지노에서 현금을 칩으로 바꾸어주는 일을 하고 있다.

이 카지노의 손님들은 칩의 갯수를 가능한 적게, 그리고 거스름돈 없이 모두 칩으로 교환하고 싶어한다.

카지노에서 사용되는 칩의 단위가 정수 배열 chips 로 주어질 때, 금액 money 를 모두 칩으로 교환한다고 하자.

이때, 가장 적은 수의 칩으로 교환했을 경우 칩의 갯수를 출력하시오.

 

 

2. 입력 설명

• 0 < money <= 10000
• 0 < chips.length <= 1000

 

3. 출력 설명

가능한 가장 적은 칩의 갯수를 정수로 반환

 

4. 매개변수 형식

• money = 3000
• chips = {1100, 500, 200, 150, 25}

 

5. 반환값 형식

5

 

 

6. 입출력 예시 설명

아래와 같이 칩으로 교환했을 때 최소의 칩의 갯수로 남는 돈 없이 교환할 수 있다.

• 1100원 2개 -> 2200 원
• 500원 1개 -> 500원
• 150원 2개 -> 300원

(1) 힌트

그리디 알고리즘 문제와 유사하나 DP 문제이다.

점화식 : dp[x] = dp[money - chips[y]] + 1

 

 

 

7. 코드 구현

import java.util.Arrays;

class Solution {
    public int solution(int money, int[] chips) {
    
    	// 해당 비용을 교환해주기 위해 필요한 칩의 갯수를 담을 배열
    	int[] dp = new int[money + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        
        // 0원을 교환하기 위해 칩은 0개가 필요하다.
        dp[0] = 0; 
        
        for(int i = 1; i <= money; i++) {
        	for(int j=0; j chips.length; j++) {
            	
                // 해당 비용이 칩을 사용할 수 있을만큼 클 때
                if( i >= chips[j]) {
                
                	// 거스름돈 없이 딱 맞춰 교환해 줄 수 있는 경우
                    if(dp[i - chips] != Integer.MAX_VALUE) {
                    	
                        dp[i] = Math.min(dp[i], dp[i - chips[j]] + 1);
                    }
                }
            }
        }
        return dp[money];
    }
}