[알고리즘풀이]백준 14916 : 거스름돈 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이전에 알고리즘 스터디에서 JAVA를 이용해 백준 14916번 거스름돈을 풀었습니다. 이를 정리해보고자 합니다.

14916번: 거스름돈

 

본문

1) 문제

14916번: 거스름돈

 

2) 과정

ATM을 풀고 풀어서 그런지 조금 더 쉽게 문제를 풀었던 것 같습니다.

이 또한 10분도 채 안되어서 끝냈던 문제입니다.

 

2-1) main

    public static void main(String[] args) throws IOException {
    	// Input
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        
        // Initialize
        int ans = -1;

	// Logic
        for(int i=n/5;i>=0;i--){
            int except5 = n-(5*i);
            if(except5%2==0) {
                ans = except5/2+i;
                break;
            }
        }
        
        // Output
        System.out.println(ans);
    }

main은 Input, Initialize, Logic, Output으로 구성됩니다.

 

Input은 이번엔 간단하게 숫자만 받아오는 문제이기도 하고 어려워 보이지 않아서 Scanner를 사용했습니다.

 

Initialize에서는 거슬러 줄 수 없다면 -1을 출력하라고 했기 때문에 ans는 -1로 초기값을 넣어줬습니다.

 

Logic부분에서는 2원동전과 5원 동전을 이용해 최소한의 동전만 사용하도록 하는 것이기 떄문에 전체값을 5로 나눈 것의 몫부터 0이 될 때까지 그 수를 줄여나가며 except5에 5원을 계산하고 남은 금액을 넣고, except5를 2로 나눈 것의 나머지가 0일 때는 ans에 except5 나누기 2의 몫과 현재 5원짜리 동전의 개수인 i를 더해준 뒤 for문을 빠져나오도록 합니다. 5원짜리 동전이 가장 많을 때부터 계산한 것이기 때문에 다른 경우를 살필 필요없이 except5를 2로 나눈것의 나머지가 없다면 종료하고 값을 출력할 수 있습니다. 

 

Output부분에서는 Logic을 통해 계산된 최소한의 동전 수 ans를 출력하며 종료합니다.

 

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

package sujeong.greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class BOJ14916 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int ans = -1;

        for(int i=n/5;i>=0;i--){
            int except5 = n-(5*i);
            if(except5%2==0) {
                ans = except5/2+i;
                break;
            }
        }
        System.out.println(ans);
    }
}

 

깃헙으로 더 자세히 보고싶으시다면, 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/greedy/BOJ14916.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비