[백준] 11047_동전 0 (Python)

11047_[문제이름] (Python)

0. 출처

• 유형 : 그리디 (silver 4)
• 링크 : 11047번: 동전 0

1. 기록

• 22/06/30 (목)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
동전의 갯수 / 가치의 합
10 4200
1
5
10
50
100
500
1000
5000
10000
50000


- 예제 출력 1 -
6

(3) 코드

import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

n, k = map(int, input().split())
temp = deque([])
answer = 0

for _ in range(n):
    v = int(input())
    if v <= k:
        temp.appendleft(v)

for money in temp:

    a = k // money
    k -= (money * a)
    answer += a
    if n == 0:
        break

print(answer)

(4) 정리

처음부터 k의 값보다 큰 동전의 가치를 지닌것은 temp 에 추가하지 않았다.
또한 가치가 큰 동전부터 나열하는 식으로 추가해서 좀 더 for문을 쉽게 돌릴 수 있도록 하였다.

(5) 참고