[백준] 11047번 동전 0 - 그리디 알고리즘 / 탐욕 알고리즘

문제

 

 

My Code

import java.io.*;

public class Main {
    static int resultNum;
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        // N, K 입력 받기
        String str = bf.readLine();
        int n = Integer.parseInt(str.split(" ")[0]);
        int k = Integer.parseInt(str.split(" ")[1]);

        int count = 0; // 동전 개수 변수 선언 및 초기화
        int[] arr = new int[n]; // 동전의 가치 배열

        // 동전의 가치 입력 받아 배열에 저장
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(bf.readLine());
        }

        //동전의 가치에서 젤 큰 값부터 탐색
        int j = n-1;
        while(k != 0){
            if (arr[j] <= k){ // 동전의 가치보다 K값이 크면 개수 세기 
                count += k / arr[j]; 
                k = k % arr[j]; // 남은 동전 값에 따라 K값 다시 저장
            }
            j--;
        }

        System.out.println(count);
    }
}

 

 

문제의 핵심 및 알게 된 점

//동전의 가치에서 젤 큰 값부터 탐색
int j = n-1;
while(k != 0){
    if (arr[j] <= k){ // 동전의 가치보다 K값이 크면 개수 세기
        count += k / arr[j];
        k = k % arr[j]; // 남은 동전 값에 따라 K값 다시 저장
    }
    j--;
}

위의 코드가 최소 동전의 개수를 저장할 수 있는 부분이다.

오름차순이 아닌 내림차순으로 동전 가치 배열을 검색하여 k값과 비교하는 것이 핵심이다.

예를 들면, k = 4200일 경우

arr[j]의 값이 1000일 때 if에 들어갈 것이다.

그럼 count += 4200 / 1000 -> 4가 더해지고

k = 4200 % 1000 -> 200이 저장될 것이다.

다시 저장된 k값으로 while반복문에서 k가 0일 때까지 진행하고 종료한다.

 

 

 

참고 강의_인프런의 Do it! 알고리즘 코딩테스트 with JAVA