[BAEKJOON] - 11047번 : 동전 0

11047번 문제 링크

문제 해석

• 각 동전들은 서로 배수 관계에 있다.
• 이 처럼 동전들의 배수관계에 놓여 잇는 경우 풀리는 대표적인 알고리즘이 '그리디 알고리즘' 이다.

⌛ 시간 복잡도

• k의 최댓값은 100,000,000 이고, n의 Ai의 최솟값은 1로, 최악의 경우 1억회 연산을 수행하게 되고, 이로인해 제한 시간 1초를 초과할 수 있습니다.

📜 로직

• 그리디 알고리즘을 적용하는 문제이므로, 최적해(가장 큰 가치의 동전)를 선택하여 연산을 수행해줍니다.
• 동적계획법(DP)을 통해서도 해결이 가능하지만, 그리디 알고리즘은 동적 계획법보다 로직이 간결해진다는 장점이 있습니다.

1. 동전들을 배열에 담습니다.
2. 오름차순으로 담았기 때문에 역으로 인덱스가 큰 수부터 차례로 연산을 수행합니다.
3. 값 k를 동전으로 나눈 뒤 몫은 결과 갯수에 담고, 나머지는 k로 초기화 해줍니다.
4. 위 로직은 k 값이 0이 될 때까지 반복 해줍니다.

😀 성공

import java.io.*;

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] s = br.readLine().split(" ");
        
        int n = Integer.parseInt(s[0]);// 갯수
        
        int k = Integer.parseInt(s[1]);//금액
        
        int[] a = new int[n];
        
        for(int i=0; i<n; i++){
            a[i] = Integer.parseInt(br.readLine());
        }
        
        br.close();
        
        int count = 0;
        
        int i = a.length - 1;
        while(k != 0){
            if(k >= a[i]){
                int tmp = k;
                
                count += (tmp / a[i]);
                
                k = tmp % a[i];
                
                i = a.length - 1;
            }
            else{
                i--;
            }
        }
        
        System.out.println(count);
    }
}