[백준] 14916 - 거스름돈 (JAVA)

1. 소요시간 : 9분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 5
4. 문제 유형 : 그리디 알고리즘, 다이나믹 프로그래밍, 수학
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/14916
8. 푼 날짜 : 2023.03.15

1. 사용한 자료구조 & 알고리즘

그리디 알고리즘을 사용했다.

2. 풀이과정

1. 우선 n을 5로 나눈 나머지가 0이면 그냥 n을 5로 나누고 출력한다.
2. 아닌 경우, while문으로 n이 0 초과인 경우마다 n을 2씩 감소시키고 비교한다.
3. n을 2 감소시켰는데 이 경우 5로 나눈 나머지가 0이라면 while 문을 빠져나간다. 이 때 원래 false인 q 가 true 가 된다.
4. while 문을 빠져나갔을 때 q가 false 인 경우라면 while 문의 조건인 n>0 이 false 가 돼서 while 문을 빠져나간 것이므로 이 경우는 -1을 출력한다.
5. 아니라면 이제 n을 5로 나눈 나머지가 0이라는 말이 되고, while 문이 돈 횟수인 count 에다 n을 5로 나눈 값을 더해준다.
6. count 를 출력한다.

3. 소스코드

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

public class Main {
	static HashSet<Integer> set=new HashSet<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();


		int n=Integer.parseInt(br.readLine());

		if(n%5==0) {
			System.out.println(n/5);
		}
		else {
			int count=0;
			boolean q=false;
			while(n>0) {
				n-=2;
				count++;
				if(n%5==0) {
					q=true;
					break;
				}

			}
			if(!q) System.out.println(-1);
			else {
				count+=(n/5);
				System.out.println(count);
			}


		}




	}

}

4. 결과

5. 회고

거스름돈 문제는 그리디 알고리즘의 기본이기에 기본에 충실하고 싶어서 쉬운 문제부터 풀어보고 있다. 이번 문제는 크게 어렵지 않았고 소요시간도 10분이 걸리지 않았다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212