동전0

https://www.acmicpc.net/problem/11047

처음 문제와 예제 입력 출력을 봤을때 이해하는데 시간이 걸렸었다. 솔직히 처음 읽었을때는 무슨말인가 하는 느낌을 받았었다. 출력부분은 K원이라고 하길래 동전으로 원을 만들어라는 말인줄 알았다. 그러다가 입력하는 저많은 숫자들이 동전크기라는걸 알고 몇개의 동전으로 입력값N의 최소값을 구하는지 이해하게 되었다.

오답

import sys

N, K = map(int, sys.stdin.readline().split())
coins = []
# 입력 값을 하나의 리스트로 만든다.
for _ in range(N):
    coin = int(sys.stdin.readline())
    coins.append(coin)

count = 0

# 입력 값 K의 값이 있을때 까지 반복 한다.
while K:
    if K // coins[-1] >= 1:
        count += K // coins[-1]
        K //= coins[-1]  # 나머지를 K값으로 저장해야되는데 몫을 저장함.
        coins.pop()
    else:
        coins.pop()
    
print(count)

처음 코드를 작성하고 출력을 했을때 아래와 같은 에러가 출력이 되었었다.

이렇게 출력이 나오니 당연히 if 문 시작에서 coins[-1] 이라는 문법 자체에 오류가 있는 줄 알았다. 내가 생각하기로는 전혀 틀린게 없는데 오류가 나오니 언어공부를 한지 얼마 안되서 확신이 없어 계속 해매게 된것 같다. 계속 저문장만 보다가 밑에 부분에서 오류가 있다는 것을 깨닫게 되었다. 그런데 밑에서 K값이 0이 되었는데 왜 다시 while문으로 들어왔는지는 모르겠다.

정답

while K:
    if K // coins[-1] >= 1:
        count += K // coins[-1]
        K %= coins[-1]  # 이 부분만 수정
        coins.pop()
    else:
        coins.pop()

큰 수에서 나머지 값을 K에 저장해서 반복문을 수행 하게 하니 정답이 출력되었다. 그리고 이러한 알고리즘 문제를 그리디 알고리즘이라는 걸 알게되었다. 그리디 알고리즘의 형태는 문제에서 표시 되다 싶이 입력값이 배수일 때에만 사용할 수 있다는 것도 알게 되었다.

마치며

이번 문제는 간단한 문제였는데 잘못된 한줄때문에 많은 시간이 소모되었다. 아직 Python 언어에 숙련도가 떨어지다 보니 오류가 나게되면 내가 작성한 문법에 대한 확신이 없다보니 더 시간이 오래 걸리는 것 같다. 알고리즘 문제 뿐만 아니라 문법에도 시간을 더 투자해야 되겠다는 생각을 더 들게 하는 문제였다.