Greedy Algorithm
- 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.
- 다만, 이렇게 구한 선택지가 항상 최적의 해를 보장하는 것이 아니다.
- 반례가 나올 수 있다.
- 그리디 알고리즘으로 풀었을 때 최적의 해가 나올지 아닐지를 고민하며 문제를 풀자.
핵심 이론
그리디 알고리즘은 다음 3단계를 반복하면서 문제를 해결한다.
- 해 선택
- 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
- 적절성 검사
- 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
- 해 검사
- 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지를 검사한다.
- 전체 문제를 해결하지 못한다면 1번으로 돌아가 같은 과정을 반복한다.
동전 개수의 최솟값 구하기 (백준 11047)
문제 분석하기
- 전형적인 그리디 알고리즘 문제이다.
- 반례없이 문제가 해결될 수 있도록 아래조건을 부여했다.
- 1≤Ai≤1,000,000,A1=1,i≥2인경우에Ai는Ai−1의배수
- 뒤의 동전 가격 Ai가 앞에 나오는 동전 가격 Ai−1의 배수가 된다는 조건을 부여했다.
- 즉, 동전을 최소로 사용하여 K를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다.
풀이
- 가격이 큰 동전부터 내림차순으로 K보다 가격이 작거나 같은 동전이 나올 때까지 탐색한다.
- 탐색을 멈춘 동전의 가격으로 K를 나눠 몫은 동전 개수에 더하고, 나머지는 K값으로 갱신한다.
- 과정 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 강의 - 인프런