Greedy Algorithm

• 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.
• 다만, 이렇게 구한 선택지가 항상 최적의 해를 보장하는 것이 아니다.
  • 반례가 나올 수 있다.
  • 그리디 알고리즘으로 풀었을 때 최적의 해가 나올지 아닐지를 고민하며 문제를 풀자.

핵심 이론

그리디 알고리즘은 다음 3단계를 반복하면서 문제를 해결한다.

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

동전 개수의 최솟값 구하기 (백준 11047)

문제 분석하기

• 전형적인 그리디 알고리즘 문제이다.
  • 반례없이 문제가 해결될 수 있도록 아래조건을 부여했다.
  • $1 ≤ A_i ≤ 1,000,000, A_1 = 1, i ≥ 2인 경우에 A_i는 A_{i-1}의 배수$
• 뒤의 동전 가격 $A_i$가 앞에 나오는 동전 가격 $A_{i-1}$의 배수가 된다는 조건을 부여했다.
• 즉, 동전을 최소로 사용하여 K를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다.

풀이

1. 가격이 큰 동전부터 내림차순으로 K보다 가격이 작거나 같은 동전이 나올 때까지 탐색한다.
2. 탐색을 멈춘 동전의 가격으로 K를 나눠 몫은 동전 개수에 더하고, 나머지는 K값으로 갱신한다.
3. 과정 1~2를 나머지가 0이 될 때까지 반복한다.

Scanner sc = new Scanner(System.in);

int N = sc.nextInt();
int K = sc.nextInt();
int A[] = new int[N];

for (int i = 0; i < N; i++) {
    A[i] = sc.nextInt();
}

int count = 0;
for (int i = N-1; i >= 0; i--) {
    if (A[i] <= K) {
        count += (K/A[i]);
        K = K % A[i];
    }

}

System.out.println(count);

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런