[Java] 거스름돈 [14916번]

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

• 예제 입력1

13

• 예제 출력1

5

• 예제 입력2

14

• 예제 출력2

4

---

• 문제 접근
  • 입력
    • 거스름돈 액수 n
  • 출력
    • 거스름돈 동전의 최소 개수
    • 거슬러 줄 수 없으면 -1
• 문제 해결
  
  • 짝수와 홀수이기 때문에 거스름돈이 5보다 작고 홀수 일 때는 거슬러 줄 수 없음
  • % 5의 나머지가 짝수일 때는 5원으로 거슬러 줄 수 있는 최대로 거슬러주고
  • % 5의 나머지가 홀수일 때는 5원으로 거슬러 줄 수 있는 최대에서 5원을 1번 덜 거슬러 줌
    → 무조건 짝수가 나옴

• 기존 풀이 [메모리 : 14196 KB / 시간 : 104 ms]

static final int TWO = 2;
static final int FIVE = 5;
public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int remainder = Integer.parseInt(br.readLine());
    int coin = 0;

    if(remainder < FIVE && remainder % 2 == 1){
        System.out.println(-1);
        return;
    }

    if(remainder % FIVE % 2 == 0){
        coin = remainder / FIVE;
        coin += (remainder % FIVE) / TWO;
    } else{
        coin = remainder / FIVE - 1;
        coin += (remainder % FIVE + FIVE) / TWO;
    }

    System.out.println(coin);
}

---

동전이 배수가 아니기 때문에 그리디로 풀 수 없다고 생각했는데 아래와 같은 방법으로 풀 수 있음

다음부터는 좀 더 생각해볼 것

static final int TWO = 2;
static final int FIVE = 5;
public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int remainder = Integer.parseInt(br.readLine());
    int coin = 0;

    while(remainder > 0){
        if(remainder % FIVE == 0){
            coin += remainder / FIVE;
            remainder = 0;
        } else{
            remainder -= TWO;
            coin++;
        }
    }

    if(remainder < 0)
        System.out.println(-1);
    else
        System.out.println(coin);
}