[백준] 11047번: 동전 0 python

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

11047번: 동전 0

 

문제 정보

문제 유형 난이도 걸린 시간 스스로 구현 성공

그리디

실버 4

15m

O

설계 방법

op이라는 list에 동전 단위 넣고 역순으로 검사

k가 i보다 클 때 k를 i로 나눈 몫을 cnt에 추가하고 나머지를 다시 k에 넣어주는 행위 반복

k가 0이면 break # 이 코드는 없어도 됨

코드

n, k = map(int, input().split())
cnt = 0
op = []
for _ in range(n):
  op.append(int(input()))
  
for i in op[::-1]:
  if k >= i:
    cnt += k//i
    k = k % i
print(cnt)

시간 복잡도

$O(n)$

어려웠던 점

조건만 잘 확인하면 쉽게 문제 풀 수 있었음

참고 자료

X