[백준 11047번] 동전0(그리디 알고리즘) python

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

11047번: 동전 0

 

<조건>
1. n(동전의 종류), k(동전의 합계) 입력 
2. k원을 만드는데 필요한 동전의 최솟값 출력

#입력
n, k=map(int, input().split())  #동전의 종류(개수), 총합
count=0   #필요한 동전의 개수
unit = [int(input()) for _ in range(n)]   

#그리디 알고리즘
while(k>0):
    c=0
    if k>=unit[-1]:
        c=k//unit[-1]
        count+=c
        k-=c*unit[-1]
    unit.pop(-1) 

#출력
print(count)

 

---

 풀이 과정

 

한 번에 풀어서 유후~하고 제출했더니 시간초과 걸렸다..

#입력
n, k=map(int, input().split())  #동전의 종류(개수), 총합
unit=[]   #동전의 단위 
count=0   #필요한 동전의 개수

for i in range(n):
    u=int(input())
    unit.append(u)

#그리디 알고리즘
unit.sort()
while(k>0):
    if k>=unit[-1]:
        k-=unit[-1]
        count+=1

    if k<unit[-1]: unit.pop(-1)

#출력
print(count)

 

 당연한 소리지만 중첩문을 쓰면 Q(n^2)이니까 시간초과가 된다...ㅋㅋ 꼭 똥인지 된장인지 찍어 먹어봐야 하는 스타일

#입력
n, k=map(int, input().split())  #동전의 종류(개수), 총합
unit=[]   #동전의 단위 
count=0   #필요한 동전의 개수

for i in range(n):
    u=int(input())
    unit.append(u)

#그리디 알고리즘
unit.sort()
while(k>0):
    while(k>=unit[-1]):
        k-=unit[-1]
        count+=1
    unit.pop(-1)

#출력
print(count)