[do it 알고리즘] 백준 11047 (그리디)

그리디 알고리즘이란?

• 현재 상태에서의 최선의 선택을 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘
• 단, 각 단계의 현재 상태 최선이 전체의 최적의 해를 보장 X
• 그리디 알고리즘을 쓸 수 있는 문제인지 아닌지 판단이 중요

문제 설명

 

풀기 전 생각

• 동전 종류를 배열에 넣기
• 뒤에서부터 즉, 큰 동전부터 비교하여 (K / 큰 동전 >= 1)이면 sum += (K / 큰 동전)
• 이후, K에는 나머지 값 (K % 큰 동전)을 대입시켜 주고 K가 0이 될 때까지 과정 반복

코드

import java.util.*;
import java.io.*;
public class Baek11047 {
    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 K = Integer.parseInt(st.nextToken());
        int[] coinArr = new int[N];

        for(int i = 0; i < N; i++){
            coinArr[i] = Integer.parseInt(br.readLine());
        }
       
        int i = N-1;
        int sum = 0;
        while(K!=0){
            if(K / coinArr[i] >= 1){
                sum += (K / coinArr[i]);
                K = K % coinArr[i];
            }
            i--;
        }
        System.out.println(sum);
    }
}

오류 및 개선 

• 통과하였지만 조건문을 굳이 (K / coinArr [i] >= 1)를 할 필요가 없음
• 가독성 있고 쉽게 (K >= coinArr [i])이면 성공!

분석

• 그리디 알고리즘은 앞서 말했듯이 현재상태에서 최선의 선택을 하는 것
• 이 문제는 최대한 큰 금액의 동전으로 구성하는 것이 최선의 선택
• 그래서 문제 조건이 A1 = 1, i >= 2일 때 Ai는 Ai-1의 배수라고 언급 중

만약 배수가 아닌 1, 3, 5의 동전이 있고 9를 만족해야 하는 문제가 있다면?
- 5원 : 1개, 1원 :4개   총합 : 5개
- 3원 : 3개                  총합 : 3개

정보처리기사에서도 나온 그리디 대표 문제!!