백준 11047번 동전0 파이썬 (python code)

난이도: 실버1
번호: 11047번

 

그리디알고리즘 문제라기 보단 가벼운 수학문제에 가까운 문제였다.

K원을 만드는 최소동전에 관한 문제였는데 각 동전이 배수관계여서 고려할 요소가 많지 않았다.

처음에는 그냥 naive하게 하나씩 뺐는데 python3는 통과못하고 pypy3만 통과해서

나눗셈으로 풀었더니 시간이 많이 단축됐다.

 

www.acmicpc.net/problem/11047

11047번: 동전 0

 

 

처음풀이(pypy3만 통과)

from sys import stdin


N,K = map(int,stdin.readline().split())
coinbox=[int(stdin.readline().rstrip()) for _ in range(N)]
numcoin = 0
for i in range(N):
    while coinbox[N - 1 - i] <= K:
        K -= coinbox[N - 1 - i]
        numcoin += 1
print(numcoin)

 

고친풀이(둘다 통과)

from sys import stdin

N,K = map(int,stdin.readline().split())
coinbox=[int(stdin.readline().rstrip()) for _ in range(N)]
numcoin = 0
for i in range(N):
    if coinbox[N - 1 - i] <= K:
        numcoin += K // coinbox[N - 1 - i]
        K = K % coinbox[N - 1 - i]
print(numcoin)