백준 11047 동전 (파이썬)


11047 동전 문제 바로가기

접근방식

  • 그리디 알고리즘을 사용하여 푸는 문제이다.
  • 처음에는 for문 안에 while문을 사용하여 k에서 금액을 빼 나아가면서 0이 될때까지 카운트를 세는 방법으로 풀었으나 Python3으로는 시간초과가 떴다. (Pyp3로는 성공이다)
  • 시간초과를 해결하기 위해 while문을 없앴고 빼는 것이 아닌 나누기를 이용하여 몫을 카운트로, 나머지를 그 다음 k로 설정하는 식으로 풀었다.

파이썬 코드

import sys

n, k = map(int, sys.stdin.readline().split())
arr = []
for _ in range(n):
    arr.append(int(sys.stdin.readline()))
c = 0
for i in range(n-1,-1,-1):
    if k == 0:
        break
    if arr[i] > k:
        continue
    # 몫을 카운트하고
    c = c + k // arr[i]
    # 나머지를 k로 변경
    k = k % arr[i]


#while문을 사용할 시 pyp3로는 성공하나 python3는 시간 초과가 뜬다.
# for i in range(n-1,-1,-1):
#     if k == 0:
#         break
#     if arr[i] > k:
#         continue
#     while True:
#         k = k - arr[i]
#         c = c + 1
#         if k < arr[i]:
#             break

print(c)





© 2020.09. by 다로

Powered by theorydb