[백준] 세탁소 사장 동혁 (BufferedReader, 그리디 알고리즘, 2720번, Java)

▶ BufferedReader & 그리디 알고리즘을 활용한 간단한 문제가 있어 정리해보고자 합니다.

 

문제설명

입력 & 출력

나의 풀이

 

이번 문제는 거스름돈을 최소한의 동전 개수로 거슬러주는 문제로, 그리디 알고리즘으로 쉽게 해결할 수 있는 문제입니다.

 

처음에는 {0.25f, 0.10f, 0.05f, 0.01f} 형식으로 해야 하나 했지만 문제를 자세히 보면 1달러는 100 센트라고 나와있습니다.

 

즉 $0.25는 25센트,  $0.10는 10센트... 이렇게 {25, 10, 5, 1} 형식의 배열로 초기화가 가능합니다.

 

현재 상태의 최적의 결과를 뽑아내려면 가장 적은 수의 거스름돈을 줘야 하기 때문에 큰 값부터 나누는 것이 중요합니다.

 

"풀이" 설명을 하자면 먼저 빠른 입력을 위하여 BufferedReader 클래스를 사용하고, 위에서 설명한 대로 동전 배열을 초기화해줍니다.

 

테스트 개수만큼 반복문을 순회하는 데 각 테스트 케이스의 거스름돈을 cost라는 변수로 받아줍니다.

 

그리고 각 거스름돈에 대한 동전 배열을 초기화해 주고, 거스름돈을 큰 값부터 (coins 배열은 내림차순이기 때문에 인덱스 0부터 시작) 나눠주고 이때 나눠준 "몫"값이 각 동전에 대한 개수이기 때문에 "몫"을 배열에 넣어줍니다.

 

그리고 거스름돈을 계속해서 나머지로 바꿔주면 됩니다.

 

마지막으로 향상된 for문을 사용하여 해당 테스트 케이스의 쿼터, 다임, 니켈, 페니의 개수를 출력하여 마무리해 주었습니다.

---

디버깅 단계 설명

1. 입력 처리
   • 3 (테스트 케이스의 수)
   • 124, 25, 194 (각 테스트 케이스의 금액)
2. 각 테스트 케이스 처리
   • 첫 번째 테스트 케이스 (124):
     • 124 % 25 = 4 쿼터 ➡️ 24 센트 남음
     • 24 %  10 = 2 다임 ➡️ 4 센트 남음
     • 4 %  5 =  0 니켈 ➡️ 4 센트 남음
     • 4 %  1 =  4 페니 ➡️ 0 센트 남음
     • 결과: 4 2 0 4
   • 두 번째 테스트 케이스 (25):
     • 25  % 25 = 1 쿼터 ➡️ 0 센트 남음
     • 0 % 10 = 0 다임 ➡️ 0 센트 남음
     • 0 % 5 = 0 니켈 ➡️ 0 센트 남음
     • 0 % 1 = 0 페니 ➡️ 0 센트 남음
     • 결과: 1 0 0 0
   • 세 번째 테스트 케이스 (194):
     • 194 % 25 = 7 쿼터 ➡️ 19 센트 남음
     • 19  % 10 =  1 다임 ➡️ 9 센트 남음
     • 9  % 5 =  1 니켈 ➡️ 4 센트 남음
     • 4  % 1 =  4 페니 ➡️ 0 센트 남음
     • 결과: 7 1 1 4

 

 

 

 

 

 

참고 ❗

[JAVA] 입출력, BufferedReader, StringTokenizer

[Algorithm] 그리디 알고리즘(탐욕법, greedy, Java) 알아보기