반응형
풀이 일시 : 2020-08-29
그리디알고리즘 :
당장 눈앞에의 최적의 상황만 쫓는 알고리즘이다.
대표적인 알고리즘으로는 가장 짧은 간선부터 연결하는 크루스칼 알고리즘이 있다.
문제 :
총 몇개의 동전을 거슬러줘야되는가? => 최소값을 구하라
풀이 :
가장 큰 단위부터 거슬러줄 수 있다면 거슬러 주는 것이 동전을 가장 적게 사용하는 방법일 것이다.
#include <iostream>
using namespace std;
//총 몇개의 동전을 거슬러 줘야되는가
int main() {
int n, result = 0;
cin >> n;
result += n / 500;
n %= 500; //나머지 연산을 해서 다음 레이어로 간다.
result += n / 100;
n %= 100;
result += n / 50;
n %= 50;
result += n / 10;
cout << result;
return 0;
}
반응형
'알고리즘 문제풀이 > 기본문제풀이' 카테고리의 다른 글
[기본문제풀이] DFS 깊이우선탐색 (0) | 2020.12.29 |
---|---|
[기본문제풀이] BFS 너비우선탐색 (0) | 2020.12.29 |
[기본문제풀이] rabin karp 알고리즘 (0) | 2020.12.28 |
[기본문제풀이] KMP알고리즘 (0) | 2020.12.28 |
[기본문제풀이] bipartite matching (0) | 2020.12.28 |
댓글