그리디

거스름돈

큰 동전부터 주면 되나

동전으로 거스름돈을 만들어 보세요. 줄 수 있는 동전 중 가장 큰 동전부터 한 개씩 줍니다.

큰 동전이 작은 동전의 배수일 때는 맞다

• 세트 A — 500 = 5 × 100, 100 = 2 × 50, 50 = 5 × 10. 큰 동전 하나는 작은 동전 여러 개와 같아서 큰 동전을 줘도 손해가 없다
• 세트 B — 4 는 3 의 배수가 아니다. 4원을 먼저 주는 바람에 3 + 3 이 될 자리를 놓쳤다
• 그래서 — 동전이 서로 배수면 큰 것부터 줘도 된다. 배수가 아니면 틀릴 수 있다

코드는 큰 동전부터 빼 나가는 것이 전부다

다음을 눌러 한 줄씩 넘기며 남은 돈이 줄고 바구니가 차는 걸 보세요. 처음 화면은 ①에서 마지막으로 한 세트 B 입니다.

같은 입력을 모든 경우로 따지면 2개(3 + 3)입니다. 큰 동전부터 준 3개(4 + 1 + 1)보다 적습니다.

• sorted(coins, reverse=True) — 동전을 큰 것부터 늘어놓는다
• while amount >= coin — 남은 돈에 이 동전을 낼 수 있는 동안 계속 낸다
• amount -= coin — 낼 때마다 남은 돈이 줄어든다. 한 번 낸 동전은 물리지 않는다

그리디에서 틀리는 자리

• 정렬을 빼면 — [1, 3, 4] 순서 그대로 6원을 주면 1원부터 줘서 6개가 된다. 큰 동전부터 줄 때는 3개다
• 배수가 아닌 세트에서는 — [1, 3, 4] 6원은 큰 동전부터 3개, 가장 적게는 2개다
• 거슬러 줄 수 없는 돈은 — [5, 10] 으로 12원을 주면 에러 없이 [10] 이 나오고 남은 2원은 말없이 사라진다. 남은 돈이 0 인지 따로 확인해야 한다
• while 대신 // 와 % — 세트 A 로 10억 원이면 while 이 200만 번 돌아 0.04초 걸린다. 몫을 amount // coin 으로 한 번에 구하면 4번 계산해 0.000003초다(Python 3.14, 컴퓨터마다 다르다)

문제에서 이 말이 보이면

다음 장에서는 끝나는 시간이 빠른 회의부터 고르는 회의실 배정을 봅니다.