[백준 11407] 동전 0

문제

 

풀이

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Main {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int tokenCount = scan.nextInt();
		int goal = scan.nextInt();
		List<Integer> tokenList = new ArrayList<Integer>();
		for (int i = 0; i < tokenCount; i++) {
			tokenList.add(scan.nextInt());
		}
        
		int count = 0;
		for(int i = tokenCount-1; i>=0; i--){
            if(goal>=tokenList.get(i)){
                count += goal/tokenList.get(i);
                goal = goal%tokenList.get(i);
            }
		}
		System.out.println(count);
	}
	
}

• 가장 큰 동전을 하나씩 선택하여 goal의 값을 줄여나간다.
• 그리디 알고리즘 대표 문제

출처 : https://www.acmicpc.net/problem/11047