코드트리 [자바 java] 동전 더하기

https://www.codetree.ai/missions/8/problems/add-coins?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 그리디 알고리즘의 기초문제이다. 

n종류의 동전으로 주어진 금액을 완성시키기 위해 필요한 동전의 개수의 최솟값을 구해야 한다. 

이 때 동전은 오름차순으로 정렬된 상태로 주어진다.

 

만들어야 하는 금액을 m이라고 하자. 

가능한 빨리 효율적으로 문제를 풀기 위해, 배열의 가장 끝에서부터 차례로 앞으로 탐색하며 탐색중인 동전으로 m에서 해당 값을 최대한 뺀다. 뺄 때 마다 답에 1을 더한다. 이를 m이 0이 될 때까지 반복하면 답을 구할 수 있게 된다.

 

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] arr= new int[n];

        for(int i = 0;i<n;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        int ans = 0;

        for(int i = n-1;i>=0;i--){
            if(m - arr[i] < 0) continue;
            while(m > 0){
                ans++;
                m -= arr[i];
                if(m - arr[i] < 0) break;
            }
        }

        System.out.println(ans);



    }
}

 

m이 500원이고, 이제 탐색할 동전이 600인 경우처럼 탐색중인 동전으로 m을 한번도 뺄 수 없을 떄의 경우를 고려하지 않아 틀렸었다.