[백준/boj.kr] 5585번 거스름돈 (C/C++, JAVA)

거스름돈 문제 보기

5585번: 거스름돈

 

Greedy 알고리즘 설명은 여기 를 참고하세요.

 

1. 문제 정의

입력으로 주어지는 X엔이 있을 때, (1000-X)엔을 500/100/50/10/5/1 엔으로 조합해 '몇 개로 잔돈을 줄 것인가'를 결정해야 합니다. 즉 최소한의 개수로 잔돈을 줄지 결정해야 하는 문제입니다.

 

 

2. 풀이 방법 탐색

'최소한'의 개수로 거스름돈을 줘야 한다면, 가장 큰 500엔부터 줘도 되는지 따져봐야 합니다. 500엔 1개로 주나, 100엔 5개로 주나 값은 똑같지만 결국 '개수가 적기 때문'이죠.

이 때, 500엔부터 시작해서 100, 50, 10, 5, 1엔 순으로 몇 개로 거스름돈을 줄 수 있을지 단계별로 정해야 합니다. 즉, 최적 부분 구조(Optimal Substructure)조건에 부합합니다. 현재 상태에서 최선의 결과를 선택해 전체에서 최적의 결과를 도출해야 하기 때문입니다.

그러면 여기서, DP로 풀지 Greedy로 풀지를 결정해야 합니다. DP와 Greedy의 가장 큰 차이는 조건에 있습니다. '이전의 선택이 이후에 영향을 주는지'가 차이점이며 영향을 준다면 DP로, 영향을 주지 않는다면 Greedy로 풀이법에 접근해야 합니다.

 

예를 들어 780엔의 거스름돈을 줘야 한다고 가정해 봅시다. 500엔 1개, 100엔 2개, 50엔 1개, 10엔 3개로 최소 7개의 동전으로 거스름돈을 줄 수 있습니다. 이 때, 500엔을 1개 고르고 100엔을 1개 골랐다고 가정한다면, 50엔은 3개를 골라야 그 순간에서 최적의 해일 것입니다. 즉, 이전의 선택(100엔을 1개 선택하고)이 이후의 선택(50엔을 선택하는 시점)에서 50엔을 1개 고를지, 2개 고를지 결정짓는게 아니라는 점입니다. 다시 말해 50엔은 100엔을 몇개 골랐든지 간에, 최적의 해를 구해야 하기 때문에 3개를 고르는게 정해져 있다는 뜻이죠.

 

이 문제는 이전의 선택이 이후의 선택에 영향을 주지 않기 때문에 DP가 아닌 Greedy로 풀이를 접근해야 합니다!

 

 

3. 풀이 순서 설계

1) Greedy로 풀 수 있는 문제인지 확인

2) 문제의 변수, 범위 파악

3) 매 순간 선택하는 방법 확인

4) 구현하기

 

1) Greedy로 풀 수 있는 문제인지 확인

앞서 2. 풀이 방법 탐색 에서 설명하였듯이, ①부분문제의 최적 결과가 전체 최적 결과를 도출한다. ②이전의 선택이 이후의 선택에 영향을 주지 않는다. 라는 조건에 부합하는 문제이기에 Greedy로 풀이가 가능합니다.

 

2) 문제의 변수, 범위 파악

문제에서 주어지는 입력인 '지불해야 할 금액'을 N이라 하면, 범위는 1 <= N < 1000 입니다.

최종 출력은 (1000-N)엔에 해당하는 최소의 잔돈 매수 입니다.

 

3) 매 순간 선택하는 방법 확인

최소의 매수로 잔돈을 거슬러 줘야 하기 때문에, 500->100->50->10->5->1 순으로 몇개를 줄지 결정합니다.

총 768엔을 거슬러 줘야 한다면,

500엔 1개 -> 100엔 2개 -> 50엔 1개 -> 10엔 1개 -> 5엔 1개 -> 1엔 3개, 총 8개로 거슬러 줄 수 있습니다.

 

4) 구현하기

for (int i = 0; i < 6; i++) {
	// i번째 배열에 있는 금액권으로 거슬러 줄 수 있는지
	if (remain >= money[i]) {
		// 몇 개의 money[i]로 거슬러 줄 수 있는지
		int num = remain / money[i];
		// (money[i] * num)빼고 남은 금액으로 변경
		remain %= (money[i] * num);

	ans += num;
	}
}

 

 

 

4-1. 최종 제출 소스(C++)

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

int N, remain, ans;
int money[6] = { 500, 100, 50, 10, 5, 1 };

int main(void) {
	scanf("%d", &N);

	remain = 1000 - N;

	for (int i = 0; i < 6; i++) {
		// i번째 배열에 있는 금액권으로 거슬러 줄 수 있는지
		if (remain >= money[i]) {
			// 몇 개의 money[i]로 거슬러 줄 수 있는지
			int num = remain / money[i];
			// (money[i] * num)빼고 남은 금액으로 변경
			remain %= (money[i] * num);

			ans += num;
		}
	}

	printf("%d\n", ans);
}

 

 

4-2. 최종 제출 소스(JAVA)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	static int ans = 0;
	static int remain = 0;
	static int[] money = {500, 100, 50, 10, 5, 1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		remain = 1000 - N;
		
		for(int i=0; i<6; i++) {
			if(remain >= money[i]) {
				int num = remain / money[i];
				remain %= (money[i] * num);
				
				ans += num;
			}
		}
        
		System.out.println(ans);
	}
}