[백준] 11047번 - 동전 0

참고: https://www.acmicpc.net/problem/11074

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

해당 문제는 그리디 알고리즘 유형으로

최적의 해를 구할 수 있다면 해당 로직을 구성하여

빠르게 문제를 푸는 방식이다.

 

잔돈의 종류는 정해져있고,

나누어 떨어질 수 있는 해가 존재하기 때문에

간단한 계산 공식으로 풀 수 있다.

 

import sys
input = sys.stdin.readline

n,k = map(int, input().split())
money = [int(input()) for _ in range(n)]
money.sort(reverse=True)
cnt = 0

for i in money:
  if i > k: continue
  cnt = cnt + (k//i)
  k %= i
print(cnt)

 

money를 리스트 컴프리헨션으로 모든 종류의 잔돈을 리스트에 담고,

해당 리스트에서 가장 큰 잔돈부터 거스름 돈을 계산할 수 있도록

역순으로 정렬한뒤, 잔돈의 갯수를 세기 위해 변수를 선언한다.

 

50000, 10000 ... 내림차순 순으로 내려가면 k원보다 크다면 건너뛰고,

그게 아니라면 잔돈의 갯수는 k원을 지폐 또는 동전으로 나눈 몫이 된다.

그리고 남은 돈을 계산하기 위해 나누어준 나머지를 다시 할당해준다.

 

그리디 알고리즘은 최적의 해를 도출해낼 수 있는 방법을 생각해내면

쉬울 수 있지만, 항상 최적의 해가 보장된다는 전제가 없기 때문에

어려울 수 있는 유형이라고 생각한다.

 

화이팅 💪