[Greedy] 백준 - 거스름돈

https://www.acmicpc.net/problem/14916

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

 

예제 입력 1 

13

예제 출력 1 

5

 

예제 입력 2 

14

예제 출력 2 

4

 

 

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        
        int result = -1; // 기본값 설정

        // 5의 개수를 최대한 활용
        for (int five = n / 5; five >= 0; five--) {
            int remainder = n - (five * 5); // 5로 나눈 후 남은 금액
            if (remainder % 2 == 0) { // 나머지가 2로 나누어 떨어질 때
                int two = remainder / 2; // 2의 개수 계산
                result = five + two; // 총 개수 계산
                break; // 첫 번째로 발견된 최적의 조합을 사용
            }
        }

        System.out.println(result);
        sc.close();
    }
}

 

그리디 알고리즘의 대표적인 문제인 거스름돈 문제!

 

처음엔 (n%5)/2 이런 식으로 접근해야했나? 했는데,

 

이 로직을 사용하면,

예를들어, 주어진 금액이 11원일 경우:

11−(5×2)=1 → 1은 5원이나 2원의 조합으로는 만들수 없다.

하지만  실제로는 5원 1개, 2원 3개로 만들 수 있는 조합이다.

따라서 잘못된 결과를 초래하는 경우가 생기는, 잘못된 알고리즘인 것이다!

 

가장 큰 단위를 먼저 사용하는 것은 맞지만, 그 이후에 남은 금액이 또 다른 조합을 만들어야 할 필요성이 있는 경우에 대해,

다양한 조합을 고려하여, 남은 금액이 적절한 조합으로 만들어질 수 있는지를 확인하는 과정이 필요했다.

올바른 접근

따라서 아래의 접근 방식을 사용했다.

1. 5원을 최대한 사용하고,
2. 남은 금액이 2로 나누어 떨어지는지 확인
3. 이를 위해 반복문을 사용하여 5원의 개수를 줄여가며 조합을 확인하는 방식이 필요했다.

---

백준은 처음 사용해봤는데,

제출이 상당히 불편하게 느껴졌다.

특히나 자바는..

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		int A,B,C;
		Scanner sc = new Scanner(System.in); 
		A = sc.nextInt();
		B = sc.nextInt();
		C = A + B;
		System.out.println(C);
	}
}

 

이런 형식으로 제출하지 않으면 오답처리 되었다.