[백준] 5585 거스름돈 - 그리디 알고리즘

그리디 알고리즘에 대해 유튜브와 티스토리를 통해 간단 학습 후 해당 알고리즘에 대한 문제를 풀어보고 싶어서 풀어본 문제!

 

📌 그리디 알고리즘 

- 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘

- 성립조건
 1. 현재 선택이 미래 선택에 영향을 미치지 않음 => 이 경우 그리디를 써도 최적 해를 찾을 수 있다. (aka 탐욕 선택 속성)

 2. 부분의 최적 해가 모이면 전체의 최적 해가 된다 (aka 최적 부분 구조)

 

 

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

 

 

이게 뭘 말하는 거냐면 ,,,,,

일단 타로는 1000원을 가지고 있는데 입력에서 "타로가 지불할 돈"은 물건 가격을 말하는 것이라고 이해했다 (맞나,,?맞아야만함)

암튼 그래서 1000원에서 입력값을 빼줘야 하는데 

예제를 보고 말하자면

1000 - 380이 거스름돈이고 그 거스름돈을 저기 동전들 골라서 거슬러줘야하는데 그 동전 개수가 최소여야한다는 말임

=> 결론은 값이 큰 동전부터 거슬러 주라는 소리 

 

📋 풀이

package algorithm;

import java.util.Scanner;
//그리디 알고리즘
public class Num5585 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //물건 가격
        int count = 0;
        int remain = 1000 - n; //잔돈
        int coins[] = {500, 100, 50, 10, 5, 1};


        for (int i = 0; i < coins.length; i++) {
            int tmp = remain / coins[i]; //해당 동전 거슬러 줄 개수
            remain %= coins[i]; //남은 돈 갱신
            count += tmp; // 최소 동전 개수를 카운트
        }
        System.out.println(count);
    }
}

 

이렇게 풀었는데 사실 동전별로 배열에 담아둔 것은 그리디 알고리즘에 대해 학습하다가 누군가의 글을 보고 스포당한 것이었음 ㅠㅠ

 

암튼 위의 설명과 이 코드를 보면 이해가 잘 갈듯 하다.

 

tmp라는 변수 하나 만들어두고 저기에 거스름돈(1000-n) / coins[i](각 동전 순회하며 몫이 존재하면 count++) 

거스름돈 갱신

방식으로 풀었다 

 

근데 풀었는데도 헷갈리는걸 보니 완전히 내것으로 만들어야겠군요,,,,💦

 

그림으로 보면 더 이해하기 쉬워서 추가해뒀습니다.