📖문제

💡입&출력 예시

❓접근

n개 종류의 값을 이용해서 k라는 수를 이용하는 전형적인 그리디 알고리즘 문제이다.
위의 접근방법을 통해 코드를 만들어 보았다.

🖥 코드(수정 전)

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coin = []
for _ in range(n):
    coin.append(int(input().strip()))

cnt = 0
while k > 0:
    now = coin.pop()
    while now <= k:
        k -= now
        cnt += 1
print(cnt)

🔥문제발생

pypy3를 통해 답안을 제출했을 때는 아슬아슬하게 통과했는데 python3를 통해 제출했을 때는 시간초과가 발생했다.
구글링 및 혼자 생각을 해봤을 때 위의 코드가 시간을 많이 잡아먹는 이유는 2가지였다.

1. 더하기, 빼기 연산을 반복문에서 일일이 수행해서
2. while문이 for문보다 연산이 느려서

1번 문제의 경우 더하기,빼기 연산을 나누기와 나머지를 더하는 식으로 해결했고
2번 문제는 while문을 for문으로 바꿔서 코드를 작성했다.(이건 별로 큰 문제는 아니었다.)

🖥 코드(수정 후)

import sys
input = sys.stdin.readline
def greedy(k, coin):
    cnt = 0
    for _ in range(n):
        now = coin.pop()
        cnt += k // now
        k = k % now
    return cnt

if __name__ == '__main__':
    n, k = map(int, input().split())
    coin = [int(input()) for _ in range(n)]

    print(greedy(k, coin))

💡결과(Python3 제출)

while문을 사용했을 때

for문 사용했을 때