«   2022/05   »
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        
Archives
Today
11
Total
83,907
관리 메뉴

차근차근

[백준 11047] 동전 0 본문

Algorithm (C++)/그리디

[백준 11047] 동전 0

SWKo 2020. 2. 5. 03:05

0. 제목

  • 백준 11047 동전 0
  • BOJ 11047 동전 0
  • C++ 11047 동전 0

1. 문제

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


2. 풀이

  • 그리디 알고리즘을 사용하였다.
  • 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다.
  • 동전의 가치가 오름차순으로 주어지기 때문에 가치가 큰 동전부터 차례대로 나눈다.
  • 몫만큼 cnt에 더해주고 K를 나머지로 갱신해준다.
  • 그렇게 모든 동전에 대해서 K/value[i]의 값이 0이 아닌동안 반복하면 누적된 cnt가 정답이다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
using namespace std;
 
int main(void) {
    int N, K;    //N: 동전의 종류, K: 가치의 합
    cin >> N >> K;
    int money;    //vector원소
    vector<int> value;
    for (int i = 0; i < N; i++) {    //오름차순 입력
        cin >> money;
        value.push_back(money);
    }
 
    int cnt = 0;    //동전의 개수
    for (int i = N - 1; i >= 0; i--) {
        while (K / value[i]) {
            cnt += (K / value[i]);
            K %= value[i];
        }
    }
    cout << cnt;
    return 0;
}

'Algorithm (C++) > 그리디' 카테고리의 다른 글

[백준 1931] 회의실배정  (0) 2020.03.06
[백준 1783] 병든 나이트  (0) 2020.03.06
[백준 10610] 30  (0) 2020.02.08
[백준 2875] 대회 or 인턴  (0) 2020.02.07
[백준 11047] 동전 0  (0) 2020.02.05
0 Comments
댓글쓰기 폼