[백준 BOJ] 5585번 거스름돈 (C++/cpp)

문제 설명

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

5585번: 거스름돈

 

접근 방법 - 그리디 알고리즘의 기초 문제

백준의 5585번 문제는 그리디 알고리즘에 있어 매우 기초적인 문제이다.

해당 문제는, 물건을 구매했을 때 받아야 할 거스름돈에 대해 받아야 할 최소 동전 개수를 출력해야 하는 문제이다.

사실 이 정도 난이도는 그리디 문제라 하기에도 우스운 정도 읍읍

가지고 있는 돈이 정해져 있기 때문에, 물건의 값을 뺀 뒤 500원부터 시작하여 1원까지 동전의 개수를 카운팅 하면 된다.

필자는 아래의 원리를 이용하여 문제를 해결할 수 있었다.

- 500->100->50->10->5->1 순으로 연산을 진행한다.
- 거스름돈에 대하여, 나눗셈 몫 연산을 한 것이 현재 단위 동전으로 환전할 수 있는 최대 개수를 의미한다.
- 거스름돈에 대하여, 나눗셈 나머지 연산을 한 것이 현재 단위 동전으로 환전되지 못한 나머지를 의미한다.

더 자세한 내용은 아래에 있으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고하길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 배열 rest를 선언하면서, 6개의 거스름돈 단위를 배열값으로 각각 저장해 둔다.

(큰 단위부터 연산을 시작해야 하기 때문에, 필자는 내림차순으로 배열값을 저장하였다.)

 

2) 물건의 값(price)을 입력받는다.

 

3) price의 값을 거스름돈 값으로 변경하여 저장한다.

(보유하고 있는 1000원에서 입력받은 price를 뺀 값을 해당 변수에 다시 저장하도록 한다.)

 

4) 동전의 최소 개수를 카운팅 할 변수 cnt를 0으로 초기화하여 선언한다.

 

5) 반복문을 실행하여, 아래의 연산을 취한다.

- price의 값이 현재 rest의 값보다 크거나 같다면, 이는 해당 단위의 동전으로 환전할 수 있음을 의미한다.

따라서 이 경우엔 아래처럼 연산을 수행하도록 한다.

- price를 현재 rest 배열값으로 나눈 몫을 cnt에 더한다. 이 값만큼 해당 동전으로 환전할 수 있음을 의미한다.
- price를 현재 rest 배열값으로 나눈 나머지를, price에 저장한다. 해당 동전으로 환전하고 남은 값으로 연산을 이어가도록 해야 한다.

 

6) 모든 연산이 완료되었다면, 최종적으로 저장된 cnt의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 5585번 코드
int rest[6] = { 500,100,50,10,5,1 };
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int price;
	cin >> price;
	
	price = 1000 - price;
	int cnt = 0;
	for (int i = 0; i < 6; i++) {
		if (price >= rest[i]) {
			cnt += price / rest[i];
			price %= rest[i];
		}
	}

	cout << cnt << endl;
}

 

제출 결과

(2022.12.26 백준 5585번 문제 제출 결과)