코테 일기(12) : 백준 [11047번] 동전 0

전형적인 그리디 알고리즘이다.

그리디 알고리즘(Greedy Algorithm) 이란?

매 선택에서 지금 이 순간 당장 최적인 답을 선택하는 알고리즘이다.

Dijkstra와 다르게 현재 노드에서 다음 노드까지만 생각하는 "오늘만 사는 알고리즘" 이라고 할 수 있다.

그래서 그리디 알고리즘 자체의 난이도가 낮을 수 밖에 없다. 

무한한 while문 속에서 현재에 해당하면 continue, 해당하지 않으면 break와 같은 극과 극의 알고리즘이다.

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <vector>

#include <stdio.h>

 

using namespace std;

 

int get_coin(vector<int> coin, int value) {

        int count = 0;

        int i = coin.size() - 1; //가장 비싼 값

        while (value != 0) { //돈이 0원이 될 때 까지

                 while(1){//가장 비싼것 부터 비교

                         if (value-coin[i] >= 0) { //동전의 크기가 value보다작으면

                                 value -= coin[i]; //계속해서 뺀다

                                 count++;

                         }

                         else {

                                 i--; //동전의 크기가 value보다 크면 다음으로 작은 동전 탐색

                                 break;

                         }

                 }

        }

 

        return count;

}

 

int main() {

        int value = 0;

        int num_coin = 0;

        scanf("%d %d", &num_coin, &value);

 

        vector<int> coin(num_coin);

        for (int i = 0; i < coin.size(); i++) {

                 scanf("%d", &coin[i]);

        }

 

        printf("%d", get_coin(coin, value));

}

난이도는 '가장 쉬움' 수준으로 별 문제 없이 풀었다.

사실 while문의 조건만 바꾸고 풀어서 복잡도를 O(n^2)에서 O(n)으로 만들면 되지만,

테스트를 통과했기 때문에 굳이 코드 수정까지는 하지 않았다.

결과