[이코테] 그리디 알고리즘 - 거스름돈(백준5585)

https://coupa.ng/caqW3b

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 취업과 이직을 결정하는 알고리즘 인터뷰 완벽

COUPANG

www.coupang.com

# 그리디 알고리즘이란?

그리디(Greedy) => 탐욕스러운

그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 을 의미합니다.

이런 그리디 알고리즘은

단순하지만 강력한 문제 해결 방법
매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
사전 지식 없이도 문제를 풀 수 있는 문제도 있겠지만, 많은 유형을 접해보고 문제를 풀어보며 훈련해야 합니다.

이코테 책에 나와있는 예제를 정리 할려고 했지만, 구글링 중에 백준에 같은 문제를 찾았습니다.

# 문제 출제 사이트

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

5585번: 거스름돈

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사

www.acmicpc.net

# 문제

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

# 입력

입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.

# 출력

제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

# 책 답안 예시(파이썬)

# 답안 예시 (자바)

BufferReader를 사용해서 입력 값을 받는다.
- BufferReader, InputStreamReader, System.in 이란?? => 참고 링크
여기서 입력 받을 때 Int형식으로 파싱하고 1000을 빼준다. [9번째 줄]
500엔, 100엔, 50엔, 10엔, 5엔, 1엔을 담는 int 배열을 선언, 초기화 해준다. [10번째 줄]
foreach 문을 통해 n(거스름 돈)을 반복문을 통해 각 동전으로 나누고 count 변수에 할당 해준다. [14번째 줄]
=> 그리기 알고리즘의 규칙에 맞게 가장 값이 큰 동전부터 체크
ex) 거스름돈이 680원이라고 하면 500원으로 나누면 1이 나온다.
1개의 500원 동전이 추가되기 때문에 count 변수에 1을 더해준다.
n % coin 을 통해 나머지 값을 n 할당 해준다. [15번째 줄]
=> 500원 짜리 잔돈을 줬다면, 그에 할당하는 값을 n(거스름 돈)에서 제외하고 다음 반복문이 돌아야 한다.