[백준 JAVA] 14916 거스름돈

14916 거스름돈

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

문제설명

주어진 금액 N을 5원과 2원 동전으로 정확히 맞추는 방법을 찾는 문제.

동전의 개수를 최소화하여 거스름돈을 맞추어야 하며 N을 정확히 맞출 수 없는 경우엔 -1 출력

접근방식

O(N/2) 시간복잡도

 

.주어진 금액을 2원씩 차감하면서 계산하므로 N이 2원으로 나누어 질 때까지의 시

문제 조건 분석 과정

 

• N이 5원으로 나누어 떨어지면 5원 동전만으로 맞출 수 있으므로, N을 5로 나눈 몫이 동전의 개수가 된다.
• N이 5원으로 나누어 떨어지지 않으면, 2원을 차감하여 가능한 경우를 찾는다.
• 동전 개수를 증가시키면서 NNN을 2원씩 차감한다.
• 5원 동전으로 나머지를 처리할 수 있는 경우엔 출력하고 아니면 -1를 출력한다.

 

•  

전체코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        //금액 입력
        int N = Integer.parseInt(st.nextToken());

        //동전의 개수
        int count = 0;

        //금액 N이 0보다 큰 경우
        while (N > 0){
            //N이 5로 나눠떨어지면
            if (N % 5 == 0){
                //N을 5로 나눈 몫만큼 동전을 추가
                count += N / 5;
                break;
            }
            //N이 5로 나눠떨어지지 않으면 2를 차감하고 동전 개수 증가
            N -= 2;
            count++;
        }

        //금액 N이 0보다 작으면 5와 2로 정확히 나눠지지 않는 경우이므로 -` 출력
        if (N < 0){
            System.out.println(-1);
        } else {
            System.out.println(count);
        }

        br.close();
    }
}