99클럽 코테 스터디 14일차 TIL

백준 - 14916번

풀이

거스름돈 동전의  최소 개수를 계산하는 것에 있어서 가장 효율적인 방법은 5원부터 사용하는 것이다.

5원으로 가능한 한 많이 나누고, 나머지 금액을 2원으로 맞춰야 한다.

 

구현 1 - 실패

import java.io.*;

public class Main {

    static final int[] COINS = {5, 2};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int count = 0;
        if (n != 1) {
            for (int coin : COINS) {
                if (n >= coin) {
                    if (n % coin == 1) {
                        count = -1;
                        break;
                    }

                    if (n % coin == 3) {
                        count = (n / coin) - 1;
                        n -= (coin * count);
                    } else {
                        count += (n / coin);
                        n %= coin;
                    }
                }
            }
        } else {
            count = -1;
        }

        System.out.println(count);
        br.close();
    }
}

모든 예제를 입력해보진 못했지만 예외를 포함한 웬만한 값은 정상적으로 출력되었다.

맞왜틀...

n의 범위가 10만까지이니 그 안에서 잘못된 값으로 출력되었을 것 같다.

 

n % coin == 1이나 n % coin == 3 조건에서 문제가 발생한 것으로 확인된다.

GPT : 위 조건은 일반화되지 않은 예외적 조건으로, 모든 경우에 대해서 최소 동전 개수를 찾는 데 적합하지 않다.

답은 얼추 맞았어도 코드를 봤을 때, 많은 조건으로 인해 사고하기 어렵고, 예외처리도 한눈에 들어오지 않는다.

 

구현 2

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int count = 0;
        
        // 2원과 5원으로 만들 수 없는 경우 
        if (n == 1 || n == 3) {
            System.out.println(-1);
            return;
        }
        
        // 가능한 경우 처리
        while (n > 0) {
            if (n % 5 == 0) {
                count += n / 5;
                break;
            }
            n -= 2;
            count++;
        }

        System.out.println(count);
        br.close();
    }
}

• 예외 처리를 가장 위에 배치하여 코드가 직관적이다. 
• 주어진 n을 5원으로 나눠 나머지가 0이 될 때까지 2원씩 감소시킨다.
• 0으로 떨어졌을 때 break를 통해 반목문을 빠르게 나올 수 있어 사고하기 편하다.

첫 번째 코드보다 가독성이 훨씬 좋고, 조건도 명확하다.

---

백준 14916번 거스름돈

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