문제: 백준 11047(동전 0)

김범수·2023년 5월 22일

greedy 백준 스택 코딩테스트 탐욕법

문제 풀이

목록 보기

4/7

백준 11047번 풀이

Greedy algorithm 실습 예제로 찾은 문제입니다. _(실버 IV)

문제 내용

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

조건

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)>

시간제한: 1초
메모리제한: 256MB

풀이 과정

문제 이해

해당 문제는 이해가 어려운 문제가 아니었습니다.
단순히 N 종류의 동전과 K원을 입력한 뒤 각각의 동전을 사용하여 가장 적은 개수로 K원을 만드는 문제입니다.

과정 풀이

동전 종류의 수N과 K원 입력
N만큼 반복하여 동전의 종류를 coinsList에 저장
K원이 0원이 될 때까지 반복 시작
현재 동전을 coin = coins.pop()으로 빼기
반복 시 마다 K -= coin을 통해 count++
최종 count 출력

위 과정대로 첨에 진행하였습니다.

구현 1

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

coins = []
for i in range(0, N):
    coins.append(int(input()))

count = 0
coin = coins.pop()
while K:
    if K >= coin:
        K -= coin
        count += 1
    else:
        coin = coins.pop()
print(count)

문제점

위 내용으로 구현하였을 때 결과가 잘 나와서 한 번에 성공할 거라 생각했지만, 시간 초과가 나타났습니다. 첨에는 당황하여 이것 저것 코드를 봤지만 이해가 되지 않아 반례가 될 법한 예외케이스 들을 확인하였습니다.
그러고 하나를 발견한 것이 다음과 같습니다.

1 100000000
1

이 케이스를 보자마자 바로 잘못된 것을 깨달았습니다.

    if K >= coin:
        K -= coin
        count += 1

해당 로직을 매 반복마다 하다보니 1원으로 반복되는 케이스는 너무 오래걸린다는 문제가 있었습니다.
그래서 다음과 같이 구현하기로 변경하였습니다.

구현2

위 내용은 두고 while에 내용만 적었습니다.

while K:
    if K % coin == 0:
        count += K // coin
        break
    if K >= coin:
        K -= coin
        count += 1
    else:
        coin = coins.pop()
print(count)

이처럼

if K % coin == 0:
        count += K // coin

해당 부분을 추가하는 것이었습니다.
그러자 원하는 케이스는 달성했지만, 진행도가 조금 더 높아졌을 뿐 시간 초과 문제가 발생했습니다.

이것도 비슷한 이유겠구나 하고 원인을 찾다가 코인이 딱 떨어지지않고 오래걸리는 경우가 존재하겠구나 라는 생각이 들었습니다.

구현3

while K:
    if K >= coin:
        count += K // coin
        K -= (K // coin) * coin
    else:
        coin = coins.pop()

해당 로직으로 처리를 하니 성공할 수 있었습니다.

정답

결국 해당 문제에 제출한 정답 코드는 다음과 같습니다.

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

coins = []
for i in range(0, N):
    coins.append(int(input()))

count = 0
coin = coins.pop()

while K:
    if K >= coin:
        count += K // coin
        K %= coin
    else:
        coin = coins.pop()
print(count)