99클럽 코테 스터디 14일차 TIL : 그리디 알고리즘(백준 14916번)

 

 

 

---

 

 

🔎 문제

춘향이 - 편의점 카운터

 

2원/5원으로만 거스름돈

동전의 개수가 최소가 되도록 거슬러주기

거스름돈이 n인 경우, 최소 동전의 개수가 몇개인지 알려주는 프로그램

 

입력: 거스름돈 액수 n (1<=n<=100,000)

 

출력: 거스름돈 동전의 최소 개수를 출력, 만약 못거슬러 주면 -1 출력

 

 

💡 풀이

package bruteforce;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Ex14916 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int answer = -1;
		
		int maxN = n/5;
		int na = n%5;
		while(maxN>=0) {
			if(na%2==0) {
				answer = maxN+(na/2);
				break;
			}
			
			maxN--;
			na+=5;
		}
		
		System.out.println(answer);

	}

}

- 최대일 때는 5원짜리 동전을 가장 많이썼을 때이기 때문에 5원짜리를 가장많이 줄 수 있는 경우의 수부터 시작함

- 5를 나눈 나머지를 2로 나눈 다음, 딱 맞아 떨어지면 해당 값을 결과로 return

- 맞아떨어지지 않으면 5원짜리 하나를 뺀 후 2원짜리 화폐를 증가하기

 

 

📌 오늘의 회고

 

어렵지 않아서 쉽게 해결할 수 있었다. !! 

그리디 알고리즘을 배우면 대표문제로 나오는 거스름돈 문제니깐 ㅎㅎ

 

요즘 회사일이든 운동이든 바빠져서 자주 못하는데 (어찌됐던 핑계ㅠㅠ)

시간내서 점심시간에라도 열심히 해야겠다 :-)