문제 : https://www.acmicpc.net/problem/5585
아주 기초적이고 대표적인 그리디 알고리즘의 예시
#include <iostream>
using namespace std;
int coin[] = {500, 100 ,50, 10, 5, 1};
int main(){
int money;
cin >> money;
int realMoney = 1000 - money;
int cnt=0;
for(int i=0; i <=5;i++){
cnt += realMoney/coin[i];
realMoney %= coin[i];
}
cout << cnt;
}
문제이다.
살짝 다른 점이라면 1000원에서 입력받은 금액을 뺀 금액을 거슬러주는 것이다.
당연히 가장 적은 숫자의 화폐로 거슬러 줘야 하기 때문에 큰 단위의 화폐부터 계산을 하면 쉽게 해결된다.
1. 화폐의 정보를 담는 int형 배열에 화폐의 금액을 담는다.
2. 금액을 입력받은 후 1000엔에서 뺀 금액을 사용한다.
3. for문을 순회하며 금액에서 화폐를 나눈 몫만큼 화폐의 개수를 의미하는 cnt를 증가시키고, 금액은 나머지 연산을 통해 재설정한다.
4. for문을 마친 후 cnt를 출력한다.
'백준 문제풀이(BOJ PS)' 카테고리의 다른 글
[백준(BOJ)] 1302번 베스트셀러 C++ (2) | 2022.07.12 |
---|---|
[백준(BOJ)] 1260번 DFS와 BFS C++ (0) | 2022.07.05 |
[백준(BOJ)] 2606번 바이러스 C++ (0) | 2022.07.05 |
[백준(BOJ)] 2839번 설탕배달 C++ (그리디 알고리즘) (0) | 2022.07.04 |
[백준(BOJ)] 2217번 로프 C++ (0) | 2022.07.04 |