첫 취준 때는 PS공부를 조금 하다가, 덜컥 어딘가를 붙었었기에, 끝까지 제대로 하지 못했었다. 이직을 준비하는 이 시점에서는, 이것이 취업을 위한 코딩 테스트다 책을 다시 제대로 해야한다고 생각했기에, 책을 첫장부터 보기로 했다.

첫장의 내용은 그리디. 사실 이론은 간단하지만, 막상 문제를 마주하면, PS 자체의 골치아픔을 너무나도 잘 드러내는 유형 중 하나다. PS는 얼핏 보면, 논리로 무장해서, 정해진 프로시저만 따라가면, 해결 되는 유형별 수학 문제집이라고 생각 할 수 도 있지만, 사실은 많이 풀어야 느는 ‘직관’으로 씨름하는 ‘논리적 눈치싸움’ 이라고 생각한다.

물론 직관도 실력이긴 하지만, 처음 내가 생각했던 PS는 그렇지 않았던 것이기에, 괜히 혼자서 배신감을 느꼈던 것이 생각이 난다.

그리고 파이썬으로 PS를 단련하는 사람으로서, 당연히 파이썬 언어의 ‘암기사항’ 들을 외워야 하는 것 또한 당연하다. 입출력, 정렬 함수의 사용법, 내장 함수의 사용법 등… 다시 하나하나 외우기 시작하다보면, 예전의 그 실력으로 돌아오고, 차곡차곡 쌓아가다 보면, PS가 커리어를 발목잡는 일은 없길 바라며, 이 PS 별관에 첫 글을 남겨본다

오늘 푼 문제 : 거스름돈

그래도 PS 블로그의 첫 글인데 PS 문제가 없으면 안되겠다. 오늘 실제로 푼 간단하지만 의미가 있는 예제를 하나 수록해보자.

500,100,50,10 원의 동전이 무한히 있다. 손님에게 거스름돈을 동전으로 주려고 하는데, 거슬러줘야 할 동전이 최소가 되게 할 때의 동전의 최소 개수를 구하라

입력

거슬러줘야 할 액수 N이 정수로 주어진다.

출력

동전을 최소로 썼을 때의 동전의 개수를 출력하라

풀이

핵심은 ‘가장 큰 동전 단위 부터 거슬러주기’ 이다. 그리디 알고리즘으로 문제를 해결할 때의 가장 중요한 부분 중 하나는, ‘그리디의 정당성’ 일 것이다.

가지고 있는 동전들에서, 큰 단위가 항상 작은 단위의 배수이기 때문에, 다른 해가 나올 수 없다. 만약 화폐단위가 500,400,100 원이라면, 800원을 거슬러주는 경우의 수를, 그리디로 큰 단위부터 하면, (500 + 100 + 100 + 100) 으로 나오겠지만, 실제 최적해는 (400 + 400) 이다. 하지만 이 문제에서는 큰 단위가 작은 단위의 배수 형태이므로, 그리디가 합당한 해결책이 되는 것이다.

정답 코드

N = int(input())
count = 0

coin_types = [500,100,50,10]

for coin in coin_types:
  count += n // coin
  n %= coin

print(count)

N = int(input())
count = 0

coin_types = [500,100,50,10]

for coin in coin_types:
  count += n // coin
  n %= coin

print(count)

여담

별개로, 아까의 큰 단위가 작은 단위의 배수가 아닌 상황에 대해서는, DP를 써서 풀 수 있다고 한다.