그리디

떄로는 당장 눈앞의 최선이, 최고의 결과를 가져온다

• 현재 차례의 최고의 답을 찾는 알고리즘
• 그리디가 어려운 이유: 왜 현재 차례에서 최고의 답이 나오는지 증명하기가 어려움
• 예: 다른 금액의 동전이 여러개 주어졌을 때 M원을 만드는 최소의 동전 개수

---

11047 동전 0

문제 링크

문제 접근

• 큰 금액의 동전부터 차감한다.

• 반례? 문제에서 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 이런 조건이 있다. 이렇게 배수가 되면 중간의 작은 것들로 나누어떨어지는 경우의 수가 없다. 그래서 이 조건 때문에 반례가 없다는 걸 증명할 수 있다.

• K를 동전 금액으로 나눈 후 남은 값으로 갱신하겠다. for루프로 돌면서 큰 값부터 K를 나누고 K가 0이 될 때까지 반복한다.

• 동전의 최대 금액은 1000000

• K의 최대 금액은 100000000 (1e8) < INT

• 동전을 저장한 뒤, 반대로 뒤집어서 내림차순으로 정렬

• 동전을 사용한 만큼 K값 갱신

전체 코드

#include<iostream>
using namespace std;

int a[11]; // 동전 종류

int main(){
	int n,k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
    	cin >> a[i];
    }
    
    int sum=0;
   
    // 오름차순으로 입력받았으므로 큰수부터 나눠준다
    for(int i = n-1; i >= 0; i--){
    	sum += k / a[i];
        k = k % a[i];
    }
    cout << sum << '\n';
}

오랜만에 쉬어가는 문제이지만 그리디는 조금만 꼬여도 어려운 문제로 출제될 수 있으니 접근 방법을 잘 기억해두자!