14916 거스름돈

처음에 간단하게 그냥 5로나누고 나머지를 2로 나눠서 나눠떨어지지 않으면 -1출력하면 되는거 아닌가? 했지만 당연히 아니다.

 

거스름돈이 13원인 경우 5원 한개 2원 4개로 거스름돈을 거슬러 줄 수 있다.

그럼 어떻게 해야할까?

 

최소한의 동전 개수로 거스름돈을 거슬러 줘야하므로

먼저 5로 나눠주고 cnt= 거스름돈 / 5 저장하고, 나머지 = n % 5

 

나머지가 2로 나눠지지 않는다면 나머지 += 5로 5원을 회수하고 cnt -= 1을 해준다. (동전 회수 했으므로 cnt도 감소해야함)

그리고 다시 5를 더한 나머지가 2로 나눠지는지 확인.... 

위 과정 반복하다가 나머지에 계속 +5를 하다보면 주어진 거스름돈의 값을 넘기는 경우에는 -1을 출력하고 프로그램 종료

 

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

public class Main{
  public static void main(String[] args) throws IOException {
    Scanner sc = new Scanner(System.in);
    long n = sc.nextInt();
    long cnt = n/5;
    long rest = n%5;
    if (rest != 0) {
        while (rest % 2 !=0){

          rest += 5;
          cnt -= 1;
          
          if(rest > n) {
            System.out.print(-1);
            return;
          }
        }
    }
    cnt += rest/2;
    System.out.print(cnt);
    
    sc.close();
  }
}

 

---

다른 사람 풀이

https://jaewoo2233.tistory.com/55

백준 No. 14916 거스름돈 JAVA

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int count = 0;
        int temp = 0;
         while(true){
             if(N%5 == 0){
                    count += N/5;
                 System.out.println(count);
                 break;
             }else{
                 N -= 2;
                 count++;
             }
             if(N < 0){
                 System.out.println(-1);
                 break;
             }
         }
    }
}

 

거스름돈이 5로 나눠지지 않을 경우 -2를 해서 5로 나눠지도록 만든다. 2원으로만 거슬러 줄 수 없는 경우에도 -2만 빼다보면 N==0이 되므로 if(N%5 == 0) 성립.

-2로 계속 빼다가 거스름돈이 음수가 될 경우 -1  출력