1183번 - 동전 자판기 자바 풀이

문제 풀이 시간 : 1시간

문제 요약

물건의 가격 W와 6종류의 동전(500, 100, 50, 10, 5, 1원)의 보유 개수가 주어짐
가지고 있는 동전을 조합하여 물건 값을 정확히 지불해야 함
이때, 사용하는 동전의 총 개수를 최대로 만드는 방법을 구하는 문제

문제 풀이

이 문제를 처음 봤을 때는 문제를 잘못 읽어 최소 동전 개수를 구하는 문제로 착각했다. 하지만 다시 읽어보니 최대 개수를 구하는 문제였고, 직관적으로 "가치가 작은 동전을 최대한 많이 사용하면 되겠다" 라고 생각했다.

📉 초기 접근 - 작은 동전부터 털어버리기

가치가 작은 동전(1원 → 5원 → ... → 500원) 순서대로 현재 가진 개수 내에서 최대한 많이 사용하여 금액을 채우는 방식으로 접근했다.

초기 코드

java

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int w = Integer.parseInt(br.readLine());
        int[] coins = new int[6];
        int[] price = {500,100,50,10,5,1};
        int[] ans = new int[6];
        int cnt = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        // 작은 동전(index 5)부터 큰 동전(index 0) 순으로 탐색
        for(int i=5;i>=0;i--){
        	if(w==0)
        		break;
            if(i==0){ // 500원짜리는 남은 금액만큼 처리
                ans[i] = w/price[i];
                cnt+=ans[i];
                break;
            }
            // 해당 동전을 최대한 많이 사용해봄
            for(int j=coins[i];j>0;j--){
                int temp = w - price[i]*j;
                // 남은 금액이 그 다음 큰 단위 동전으로 나누어 떨어져야 한다는 조건 (검증 부족)
                if(temp%price[i-1]!=0)
                    continue;
                
                w = temp;
                ans[i] = j;
                cnt+=j;
                break;
            }
        }
        System.out.println(cnt);
        for(int i=0;i<6;i++){
            System.out.print(ans[i]+" ");
        }
    }
}

하지만 이 방식은 치명적인 반례가 존재했다. 작은 동전을 무작정 다 써버리면, 남은 금액을 큰 동전으로 메울 수 없는 상황이 발생한다.

반례 상황

plain text

입력
10046
21 1 1 6 11 2  (500원:21개, ..., 1원:2개)

내 코드의 결과는 36개 (19 0 1 4 11 1)가 나왔지만, 실제 정답은 30개 (20 0 0 0 9 1) 여야 했다.

👉 왜 실패했나? 작은 동전을 우선적으로 사용하다 보니 마지막에 남은 큰 금액(500원 단위 등)을 처리할 때 "딱 나누어 떨어지지 않는" 상황이 발생해 억지로 덜 최적화된 조합이 출력되는 오류가 있었다.

개선 아이디어 - 남길 돈을 최소화하자

문제를 다시 정의해보았다. 우리는 "지불할 동전의 개수를 최대화" 해야 한다. 이 말은 즉, "내 주머니에 남길 동전의 개수를 최소화" 하는 것과 같다.

내가 가진 돈의 총액(Total)을 구한다.
Total - W = 내가 남겨야 할 돈(Remain) 을 계산한다.
Remain을 만들 때 동전 개수를 최소로 하려면? 👉 가장 큰 단위의 동전(500원)부터 최대한 많이 남기면 된다.

이 방식을 사용하면 복잡한 예외 처리 없이 아주 깔끔하게 해결된다.

핵심 로직

입력받으며 total 금액 계산
remain = total - w 계산
큰 화폐 단위(500원)부터 순회하며:

최종 코드

java

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int w = Integer.parseInt(br.readLine());
        int[] coins = new int[6];
        int[] price = {500,100,50,10,5,1};
        int[] ans = new int[6];
        int cnt = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());

        int total = 0;
        // 1. 가진 돈의 총액 계산
        for(int i=0;i<6;i++){
            coins[i] = Integer.parseInt(st.nextToken());
            total += coins[i] * price[i];
        }
        
        // 2. 남겨야 할 금액(Remain) 계산
        int remain = total - w;
        
        // 3. 큰 동전부터 최대한 많이 남기기 (남는 동전 최소화 -> 지불 동전 최대화)
        for(int i=0;i<6;i++) {
        	int maxKeep = remain / price[i]; // 이 동전으로 채울 수 있는 최대 개수
        	int keep = Math.min(coins[i], maxKeep); // 실제 가진 개수와 비교
        	
        	remain -= price[i] * keep; // 남길 금액에서 차감
        	
        	ans[i] = coins[i] - keep; // 지불할 동전 = 가진 것 - 남길 것
        	cnt += ans[i];
        }
        
        System.out.println(cnt);
        for(int i=0;i<6;i++){
            System.out.print(ans[i]+" ");
        }
    }
}

1183번 - 동전 자판기

문제 풀이 시간 : 1시간

문제 요약

문제 풀이

📉 초기 접근 - 작은 동전부터 털어버리기

초기 코드

개선 아이디어 - 남길 돈을 최소화하자

핵심 로직

최종 코드

함께 읽으면 좋은 글

2543번 - 타일 채우기

택배상자

롤케이크 자르기

할인 행사