[백준] 거스름돈(5585)

대표적인 그리디 알고리즘 문제

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scan = new Scanner(System.in);
		int money [] = {500,100,50,10,5,1};
		int n=scan.nextInt();
		int result=0;
		n=1000-n;
		
		for(int i=0;i<money.length;i++){
			int coin = money[i];
			result += n/coin;
			n=n%coin;
		}
		System.out.println(result);
		
		
	}
}

배열안에 잔돈을 넣는다.

그리고 가장 큰 동전부터 시작해서 n/coin으로 동전의 개수를 구한후 result에 더해준다. 그리고 n%coin을 통해 나머지 잔돈을 구한다.