2720번 문제 : 세탁소 사장 동혁

2720번: 세탁소 사장 동혁 (acmicpc.net)

2720번: 세탁소 사장 동혁

자바

생각보다 간단했던 문제. 화폐값들을 내림차순으로 배열에 담아놓고

반복문으로 배열요소를 돌면서 거스름돈으로 주어진 값에 계속해서 나눠감.

몫(dshare)을 거스름돈/배열요소 값으로 지정해놓고

StringBuilder에 append함.

 

그리고 *change는 방금 구한 dshare에서 배열요소 (화폐 가격)을 곱한 값을 빼줘야함. 그래야 또 그 나머지로 다음 화폐가 얼마나 필요한지 구할 수 있으니까

 

근데 이제 화폐가 실수이다보니 double형 배열로 선언을 헀기 때문에 double과 연산을 해줄 수인 거스름돈 change도 double형으로 선언하였다. 그러고 나니까 *연산을 헀을 때 실수가 나와서 String.format으로 반올림을 해주었당

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Main{
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int T = Integer.parseInt(br.readLine());
    	double arr[] = {0.25,0.10,0.05,0.01};
    	
    	StringBuilder sb = new StringBuilder();
    	for(int i=0;i<T;i++) {
    		double change = Integer.parseInt(br.readLine());
    		change = change*0.01;
    		for(int j=0;j<arr.length;j++) {
    			int dshare = (int)(change/arr[j]);
    			sb.append(dshare+" ");
    			change -= dshare*arr[j];
    			change = Double.parseDouble(String.format("%.2f", change));
    			//change = Math.round(change*100)/100;
    		}
    		sb.append("\n");
    	}
    	System.out.println(sb);
 	}
}

댜른 사람들 풀이를 찾아보니까 그리디 알고리즘 문제라고 한다 !

 

알고리즘 관련해서 .. 추가 공부가 필요할 거 같다

 

알고리즘 - 나무위키 (namu.wiki)