탐욕법 - Greedy

✏️ 탐욕법이란?

📍 기본 이론

• 현재 상태의 선택지 중 최선의 선택지를 계속 선택하면 전체의 선택지중 최선의 선택일거라 가정하는 알고리즘 이다.

📍 탐욕법을 사용할 수 있는 조건

1. 현재의 선택이 미래의 선택에 영향을 주지 않는경우
2. 부분의 초적 해가 모여 전체의 최적 해가 되는 경우

• 위 2가지 조건을 만족할 때 어떻게 정렬해야 합리적인 선택을 할 수 있을지 고민 후 탐욕법을 적용한다.

📍 핵심 이론

• 그리디는 3단계를 반복하며 문제를 해결한다.
  1. 해 선택
     • 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
  2. 적절성 검사
     • 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
  3. 해 검사
     • 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다.
     • 해결하지 못한다면 1번으로 돌아가 반복한다.

✏️ 대표적인 그리디 문제

🔗 백준 11047 : 동전 0

📍 주의 사항

• 그리디 알고리즘을 사용할 땐 항상 반례를 고민해야 한다.
• 문제에서는 동전을 최소로 사용해 가치의 합을 K 로 만들것을 요구한다.
  • 그리디를 사용하면 최소의 동전이 필요하므로 가장 가치가 높은 동전부터 선택하게 된다.

조건)
목표 = 9
동전 = { 1, 3, 5}

• 자연스럽게 최초에 가지 5를 가진 동전을 선택하게 되고,
  1의 가치를 가진 동전 4개를 사용해 총 5개의 동전이 선택되게 된다.
  - 하지만 이 경우 3의 가치 동전 3개로 문제를 해결할 수 있다.
  - 즉, 문제를 읽고 그리디로 해결할 수 있는 문제인가를 잘 판단해야 한다.
• 문제의 조건에서는 A[i] 는 A[i - 1] 의 배수라는 조건이 있는데,
  이 경우엔 위와같은 반례가 나올 수 없다.
  - 따라서 그리디를 사용할 수 있는 문제가 된다.

📍 문제 풀이

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

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());
        long K = Integer.parseInt(st.nextToken());

        long[] A = new long[N];
        int count = 0;

        for (int i = 0; i < N; i++)
            A[i] = Long.parseLong(br.readLine());

        // 탐욕법 시작
        for (int i = N - 1; i >= 0; i--)

            // 목표보다 적을 경우
            if (K >= A[i]){

                // 나머지와 몫을 구함
                count += K / A[i];
                K = K % A[i];

                // 목표가 0 이면 반복 종료
                if (K == 0) break;
            }
        System.out.println(count);
    }
}