백준 - 11047(그리디 알고리즘)

그리디 알고리즘의 그리디가 Greedy라는 것을 오늘 처음 알았다.

일단 뒷일 생각하지 않고 일단 눈앞에 닥친 최적값 부터 구하고 보는 것이다.

난 지금까지 Dynamic Programming을 그리디 알고리즘으로 풀고 있었다는 것을 깨달았다.

그 이유는 다이내믹 프로그래밍을 푸는 루틴과 똑같이 풀었는데 금방 답을 찾아냈기 때문이다.

 

import sys

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

arr = []
for i in range(n):
    arr.append(int(sys.stdin.readline()))

arr.sort(reverse=True)
temp =0
cnt = 0
while k != 0:
    for i in arr:
        if k - i >= 0:
            temp = k // i
            if temp != 0:
                k = k - (i * temp)
                cnt = cnt + temp
                break
            else:
                k = k-i
                cnt = cnt +1
                break

            if k == 0:break



print(cnt)

다이내믹 프로그래밍을 다시 공부할 필요성을 느낀다.