[C++] 백준 5585 : 거스름돈

그리디 알고리즘

이 문제를 그리디 알고리즘으로 해결할 수 있는 이유는, 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보기.

#include <iostream>

int main(void){ // 그리디 알고리즘
    int n, coin = 0, money = 1000;
    int coin_type[6] = {500, 100, 50, 10, 5, 1};
    scanf("%d", &n);

    money -= n;
    
    for(int i = 0; i < 6; i++){
        coin += money / coin_type[i];
        money %= coin_type[i];
    }
    
    printf("%d", coin);

    return 0;
}

나눠줘서 거스름돈의 개수를 구하고 남은 거스름돈은 나머지를 사용해 계산할 수 있다.

코드 복잡도

O(N) : for문 하나.

오늘의 키포인트

• 런타임 에러 (OutOfBounds) 발생 : for문 안을 배열의 크기를 구하는 sizeof(coin_type) 대신 6을 넣으니까 해결. 생각보다 이런 작은 계산 하나도 큰 부담이 되나보다.