파이썬 알고리즘 141번 | [백준 11047번] 동전 0 - 그리디

141. 동전 0

1) 어떤 전략(알고리즘)으로 해결?

• 그리디 알고리즘

2) 코딩 설명

• 가장 큰 동전부터 돌아가면서 해결

<내 풀이>

# 동전 갯수 최솟값 : 액수가 큰 동전부터 체워넣기
# 기준에 따라서 가장 좋은 것을 선택하는 그리디 알고리즘
from re import T
import sys

n, k= (map(int,sys.stdin.readline().split()))
coin = []

for i in range(n):
    coin.append(int(input()))

coin.sort(reverse=True)

present = 0
cnt = 0 

while k>0 :
    if k-coin[present] < 0 and present+1 < len(coin) :
        present+=1
    else : 
        cnt+=k//coin[present]
        k%=coin[present]
        

print(cnt)

<내 틀린 풀이, 문제점>

1) 시간초과
=> 왜냐 뺄셈과 덧셈으로 작업을 했기 때문이지

# 동전 갯수 최솟값 : 액수가 큰 동전부터 체워넣기
# 기준에 따라서 가장 좋은 것을 선택하는 그리디 알고리즘
from re import T
import sys

n, k= (map(int,sys.stdin.readline().split()))
coin = []

for i in range(n):
    coin.append(int(input()))

coin.sort(reverse=True)

present = 0
cnt = 0 

while k>0 :
    if k-coin[present] < 0 and present+1 < len(coin) :
        present+=1
    else : 
        k-=coin[present]
        cnt+=1

print(cnt)

<반성 점>

• 덧셈과 뺄셈은 참 오래걸리니 지양하자

<배운 점>

% 는 나머지
// 는 몫