[BOJ / C++] 동전 0 (그리디)

문제링크: https://www.acmicpc.net/problem/11047

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<int> coin(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> coin[i];
    }

    int cnt = 0;
    for (int i = n-1; i >= 0; i--) {
        cnt += k / coin[i];
        k %= coin[i];
    }
    cout << cnt;
}

 

 

2. 분석

문제에서 동전이 오름차순으로 주어지고, 동전의 가치에는  A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수라는 조건이 있으므로 그리디 풀이로 접근이 가능하다. k에서 가장 큰 값부터 시도해보면 된다.

 

3. 시간복잡도

한번만 순회하므로 O(n)이고, n = 10 < 10^8 이므로 시간제한 1초 내에 통과 가능하다.