백준알고리즘 11047 동전 0 풀이 C++

https://www.acmicpc.net/problem/11047

11047번: 동전 0

매 순간 당장 최적인 수를 선택하여 최소로 필요한 동전 수를 구하는 점에서 그리디 알고리즘문제이다. 

 

정답코드 (C++)

---

#include <iostream>

using namespace std;

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N, K, index, res = 0;
    cin >> N >> K;
    int arr[10] = {0, };

    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }

    while (K != 0){
        for (int i = N - 1; i >= 0; i--){
            if (K >= arr[i]){
                res += K / arr[i];
                K = K % arr[i];
            }
            if (K == 0) break;
        }
    }
    cout << res;
}

 

첫 제출에 시간 초과가 뜨길래 cin과 cout에 소요되는 시간때문이라 생각했다. 

ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

그래서 C와 C++ 표준 stream 동기화를 끊는 코드를 다음과 같이 추가했으나 여전히 시간초과였고 while문 선언이 문제란 것을 깨달았다.

    while (K != 0) {
        for (int i = 0; i < N; i++) {
            if (K < arr[i + 1]) {
                K = K - arr[i];
                break;
            }
        }
        res++;
    }
    cout << res << endl;

4200원에 필요한 동전 갯수를 1개 카운트 할 때 마다 매번 for문이 다시돈다 알고리즘 공부를 몇달만에 다시 시작했기 때문인듯하다.  당연히 시간초과가 걸리는 코드였다.

 

그러나 덕분에 C++ 입출력속도에 대한 고민을 해볼 수 있었고, endl이 버퍼를 비우는 작업까지 동반해 '\n' 보다 현저히 느리다는 것도 알았다. 

 

https://www.acmicpc.net/blog/view/56

입력 속도 비교