BAEKJOON 5585번 거스름돈👛

알고리즘 3주차 첫번째 문제!!

👛 그리디 알고리즘 <거스름돈 문제> 👛

📌그리디 알고리즘이란?
그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 이름에서 알 수 있듯이 어떤 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이란 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다.

구글링을 했을 때 가장 이해하기 쉬운 그림을 가져왔다.

위의 사진을 함께 보면 7을 따라가면 107이라는 숫자를 얻게되지만 13을 따라가면 24라는 숫자를 얻게된다.

멀리 바라봤을 때에는 7을 따라가는 것이 이득이라고 생각하겠지만 그리디 알고리즘은 현재 주어진 상황에서만 을 생각하기 때문에 13을 따라가게 된다.

—> 이것이 그리디 알고리즘 = 눈앞의 이득을 따라감

코딩테스트에서 주로 나오는 문제 유형 중 하나로 알려져있는 그리디 알고리즘 스터디에서 다루게 되어서 다행이다! 대표적인 거스름돈 문제를 풀어보았다!

백준 문제 링크
https://www.acmicpc.net/problem/5585

가장 큰 화폐단위부터 돈을 거슬러 주는 것이 포인트인 문제이다. 내가 풀이한 코드는 아래와 같다.

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

public class Change_5585 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 거스름돈 알고리즘
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int pay = Integer.parseInt(br.readLine());
		int coin[] = {500,100,50,10,5,1};
		int count = 0;
		int change = 1000 - pay;
		for(int i=0;i<coin.length;i++) {
			count += change / coin[i];
			change = change % coin[i];
		}
		System.out.println(count);
	}
}

입력하는 값을 scanner를 사용하지 않고 BufferReader를 사용한 이유는 처리 속도를 빠르게 하기 위해서 사용했다.

풀이방법은 아래와 같이 진행하였다.

1. BufferReader를 통해 지불해야 할 값을 입력받는다.
   입력받은 값은 String형태로 들어오기 때문에 Integer.parseInt를 사용해 int형태로 바꿔준다.
2. 거스름돈의 단위를 배열에 저장한다.
3. 거스름돈의 개수를 셀 count를 기본값인 0으로 설정 선언해준다.
4. 1000원에서 지불해야할 pay를 뺀 거스름돈을 change라는 변수에 저장해준다.
5. for문을 이용해 배열에 저장된 거스름돈의 단위만큼 반복계산한다.
   - 거스름돈의 단위로 나눈 정수값을 count에 더해 넣어준다.
   - 거스름돈의 단위로 나눈 나머지값을 change로 바꿔준다.
6. for문이 모두 돌았으면 count의 값을 출력해준다.

나의 풀이는 이러하다. 아마 나보다 더 빠르게 풀이한 코드가 있을 듯 하니 그것을 보러 가봐야겠다 ㅎㅎㅎ 구글링과 다른사람 코드 안보고 풀기 성공 🎈

이런 뿌듯함때문에 코딩을 하는 것 아니겠는가~ 이제 다음 문제를 풀러 가봐야겠다 ㅎㅎㅎㅎ