알고리즘 문제 풀이: 파이썬/BOJ

[BOJ_14916] 거스름돈

hueco 2022. 8. 21.

 

📌 문제 링크: https://www.acmicpc.net/problem/14916

 

14916번: 거스름돈

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

www.acmicpc.net

 

내 풀이(Success) :

 

🧐 Review:

 그리디 문제의 대표 유형인 거스름돈 문제이다. 입력값으로 주어진 N원을 2원과 5원의 동전으로 거슬러 줄 때, 거슬러 주는 돈의 개수를 최소한으로 만들어 반환해주면 되는 문제이다. 단순하게 생각해보면 5원의 개수를 최대한으로, 2원의 개수를 최소한으로 한다면 거슬러주는 동전의 개수를 최소한으로 만들 수 있다. (만약 입력값으로 10원이 주어졌다면 2원 동전 5개로 거슬러 줄 수도 있지만, 5원 동전 2개로 거슬러 주는 것이 더 적은 동전을 사용한다.)

이 아이디어를 갖고, 동전을 5원으로 먼저 거슬러 주고, 남은 돈을 2원으로 거슬러 주는 경우와 그 반대의 경우를 모두 확인해서 result 배열에 담는다. 다음으로 배열이 비어있으면 5원과 2원으로 거슬러 줄 수 없는 경우(N이 1원 or 3원)이므로 문제의 조건대로 -1을 출력하고, 배열이 비어있지 않다면 배열에서 가장 최솟값을 출력한다. 

 문제를 풀고나서 다른 사람들의 풀이를 확인해보니 내 풀이보다 좀 더 그리디 문제답게 푼 코드들을 확인했다. 해당 알고리즘 문제를 더 많이 풀어서 나도 그렇게 생각할 수 있는 사고력을 키워야겠다.

 
 
 
 
 

'알고리즘 문제 풀이: 파이썬 > BOJ' 카테고리의 다른 글

[BOJ_1931] 회의실 배정  (0) 2022.08.27
[BOJ_2003] 수들의 합 2  (0) 2022.08.27
[BOJ_16953] A -> B  (0) 2022.08.20
[BOJ_21921] 블로그  (0) 2022.08.16
[BOJ_11659] 구간 합 구하기 4  (0) 2022.08.15

댓글