[백준 11047번 C/C++] 동전 0
[백준 11047번 C/C++] 동전 0

https://www.acmicpc.net/problem/11047
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
해결전략
탐욕 알고리즘 (Greedy Algorithm)
탐욕 알고리즘 해결전략
- 문제에 따라 최적해의 구성 요소를 선택하기 위한 기준을 정한다.
- 초기 해답을 비어있는 상태 또는 어떠한 형태로 설정한다.
- 선택 기준에 따라 해답에 요소를 추가하거나 선택한다.
- 선택한 요소를 기준으로 다음 요소를 선택한다.
- 만약 해답이 완성되지 않았다면 3단계부터 반복한다.
- 모든 요소를 선택하고 해답이 완성되었을 때, 최종 해답을 반환한다.
코드
#include<iostream> using namespace std; int n, k, input, cnt; int coin[11]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(NULL); cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> input; coin[i] = input; } for (int i = n; i > 0; i--) { while (k >= coin[i]) { k -= coin[i]; cnt++; } if (k <= 0) break; } cout << cnt; return 0; }
더 나은 풀이
#include<iostream> using namespace std; int n, k, cnt=0; int coin[11]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> coin[i]; } for (int i = n; i > 0; i--) { if (k == 0) break; cnt += k / coin[i]; k %= coin[i]; } cout << cnt; return 0; }
'⭐ 코딩테스트 > 백준' 카테고리의 다른 글
[백준 1463번 C/C++] 1로 만들기 (0) | 2023.06.15 |
---|---|
[백준 11866번 C/C++] 요세푸스 문제 0 (0) | 2023.06.14 |
[백준 1874번 C/C++] 스택 수열 (0) | 2023.06.12 |
[백준 1181번 C/C++] 단어 정렬 (0) | 2023.06.10 |
[백준 11650번 C/C++] 좌표 정렬하기 (0) | 2023.06.09 |
댓글
이 글 공유하기
다른 글
-
[백준 1463번 C/C++] 1로 만들기
[백준 1463번 C/C++] 1로 만들기
2023.06.15 -
[백준 11866번 C/C++] 요세푸스 문제 0
[백준 11866번 C/C++] 요세푸스 문제 0
2023.06.14 -
[백준 1874번 C/C++] 스택 수열
[백준 1874번 C/C++] 스택 수열
2023.06.12 -
[백준 1181번 C/C++] 단어 정렬
[백준 1181번 C/C++] 단어 정렬
2023.06.10
댓글을 사용할 수 없습니다.