티스토리 뷰

알고리즘/BOJ

BOJ 11047번, 동전 0

아테즈 2018. 10. 20. 20:59

문제 풀이에 사용된 것은 Greedy Method로, 매 순간마다 최적의 해를 추구하는 방법이라 저렇게 이름이 붙었습니다.

편의점이나 카페에서, 잔돈을 거슬러 주는 방법과 유사합니다.
되게 직관적이죠.

예를 들어, 490원을 10원, 50원, 100원, 500원으로 남겨주는 방법의 개수를 찾는다면?

다음과 같은 방법이 있을 수 있습니다.
a. 10원짜리 49개.
b. 100원짜리 4개, 10원짜리 9개
c. 100원짜리 4개, 50원짜리 1개, 10원짜리 4개
등등...

이미 깨달으신 분도 계시겠지만, 큰 돈부터 먼저 채워나가면 동전의 개수를 최소화할 수 있습니다. 아래는 그 소스코드 입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
int main() {
    vector<LL> v;
    LL n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) {
        LL temp; cin >> temp;
        v.push_back(temp);
    }
    reverse(v.begin(), v.end());
    LL idx = 0;
    LL gesu = 0;
    while (m != 0) {
        while (true) {
            if (m >= v[idx]) {
                m -= v[idx];
                gesu++;
            }
            else {
                idx++;
                break;
            }
        }
    }
    cout << gesu;
    return 0;
}
cs


'알고리즘 > BOJ' 카테고리의 다른 글

BOJ 7576, 토마토  (0) 2018.10.22
BOJ 14731번, 謎紛芥索紀 (Large) - (미분개색기)  (0) 2018.10.20
BOJ 2293번, 동전 1  (0) 2018.10.20
BOJ 2294, 동전 2  (0) 2018.10.20
BOJ 14754, Pizza Boxes  (0) 2018.10.20
댓글
댓글쓰기 폼
공지사항
Total
23,335
Today
0
Yesterday
10
링크
TAG
more
«   2022/11   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30
글 보관함