[코딩테스트] 백준 11047번: 동전 0

-문제: https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

-정답풀이: 

n,k=map(int,input().split())
data=[]
for _ in range(n):
    data.append(int(input()))
count=0
answer=0
for i in range(n-1,-1,-1):
    if data[i]<=k:
        count=k//data[i]
        k-=count*data[i]
        answer+=count
print(answer)

• 문제의 다음과 같은 조건 때문에 그리디로 풀 수 있다 

 

• 주어진 k보다 작은 수 중에 가장 큰 수를 구해서 나누면 그 몫이 해당수의 개수이다
• 나머지를 다시 k에 대입하고 같은 방법으로 반복한다 

-틀린 풀이: 

 

 

• 이전에 공부했던 내용으로 풀었더니 시간초과가 발생했다.