[swexpert] 1970. 쉬운 거스름돈 (python, java)

그리디 대표 알고리즘입니다

가장 큰 금액부터 나누면 잔돈 개수는 가장 적게 나옵니다 ><

 

1. 파이썬 풀이

t=int(input())
change=[50000,10000,5000,1000,500,100,50,10]
for i in range(1,t+1):
    print(f'#{i}');
    money=int(input())
    result=[0]*len(change)
    for j in range(len(change)):
        result[j]=money//change[j]
        money%=change[j]
    print(*result)

 

 

2. java 풀이 

 

import java.util.Scanner;

public class Solution {
	
	static int[] money= {50000,10000,5000,1000,500,100,50,10};
	static int[] change=new int[8];
public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {		
			int n=sc.nextInt();
			System.out.printf("#%d\n",tc);
			for (int i = 0; i < money.length; i++) {
				change[i]=n/money[i];
				n%=money[i];
			}
			
			for (int c:change) {
				System.out.printf("%d ",c);
			}
			System.out.println();
		}
		sc.close();
	}
	
	
}