[백준 11047번 C/C++] 동전 0
목차
[백준 11047번 C/C++] 동전 0
https://www.acmicpc.net/problem/11047
해결전략
탐욕 알고리즘 (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