[BOJ 11047] 동전 0 - JAVA

그리디 문제인 동전 0 문제를 풀어보았습니다.

이 방법은 개인적인 방법이며 최적의 솔루션이 아닐 수 있습니다.

 

구현내용

 

 

구현방법

이 문제에서 집중해야할 포인트는 두 가지가 있습니다.

 

- 가장 먼저 그리디 문제라는 것 입니다. 이것만 파악하셨다면 반이상은 풀었다고 보시면 됩니다.

- 두번째는 동전의 가치가 오름차순으로 주어진다는 것입니다.

 

 

코드를 보며 주석을 통해 자세한 설명을 보실 수 있습니다.

↓↓↓↓↓↓↓↓↓↓          ↓↓↓↓↓↓↓↓↓↓↓↓↓       ↓↓↓↓↓↓↓↓↓↓↓↓

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 입력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 출력

        int count = 0; //동전 개수

        StringTokenizer stok = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stok.nextToken());
        int k = Integer.parseInt(stok.nextToken());

        int[] list = new int[n]; // 동전 List
        for(int i=0;i<n;i++){
            list[i] = Integer.parseInt(br.readLine());
        }
        int i = n-1; //그리디는 큰 수 부터 봐야하기 때문에 List의 내림차순으로 확인한다.
        while(true){
            if(list[i]<=k){ //큰 수부터 차례대로 k보다 작거나 같은 수로 k의 값을 줄여나가며
                            // count를 합니다.
                k-=list[i];
                count++;
            }
            else{
                i--;
            }
            if(k == 0)  //반복문 탈출 조건은 k가 줄어들다가 0이 되었을 시점입니다.
                break;
        }
        bw.write(String.valueOf(count)); //출력
        bw.flush();
    }
}