[알고리즘]_그리디 알고리즘_거스름돈(No. 14916)

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

---

입력
첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

---

출력
거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

---

코드

import java.util.Scanner;

public class No_14916 {
	public static void main(String[] args) {
		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);
	}
}

마무리

• 풀이를 찾아보니 이렇게 간단한 문제를 빙빙 돌려서 풀고 있었다,,,^^
  i를 1부터 시작해서 풀어서 코드도 세상에서 제일 복잡해지고 틀림= 근데 왜 틀렸는지 모름
  총체적 난국이다 힝 엉망진창 내 코드 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

  		int n=sc.nextInt();
  		int money=n;
  		int min=Integer.MAX_VALUE;
  		int count=0;
  
  		if(n/5!=0&&n%5==0){
  			System.out.println((n/5));
  		}else if(n/5!=0){
  			for(int i=1;i<=n/5;i++){
  				money-=5;
  				count=i;
  				if(money%2==0&&money/2!=0){
  					count+=money/2;
  					if(min>=count){
  						min=count;
  					}
  				}
  
  			}
  			if(min==Integer.MAX_VALUE){
  				if(n/2!=0&&n%2==0){
  					System.out.println(n/2);
  				}else{
  					System.out.println(-1);
  				}
  			}else{
  				System.out.println(min);
  			}
  		}
  	}

참고
https://codingjerk-diary.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%ED%92%80%EC%9D%B4%EB%B0%B1%EC%A4%80-14916-%EA%B1%B0%EC%8A%A4%EB%A6%84%EB%8F%88-JAVA