[이코테] 다이나믹 프로그래밍 실전문제 3번

import sys
from sys import stdin
from collections import deque
sys.setrecursionlimit(10 ** 8)
sys.stdin.readline 

N = int(input())
array = list(map(int,sys.stdin.readline().split()))
d = [0] * 101

d[0] = array[0]
d[1] = max(array[0],array[1])
for i in range(2,N):
    d[i] = max(d[i-1],d[i-2] + array[i])

print(d[N-1])

재귀함수의 스택 크기가 한정되어있을 수 있으므로, bottom - up 방식을 이용하여 구현하는 것이 활용적이다.

그래서 피보나치 수열에서도 초항과 두번째 항을 정해주므로 

d[0]과 d[1]을 정의해주어야 한다

d[0]는 array[0]값과 같아야 하고

d[1]은 문제에서 강탈할 수 있는 "최댓값"을 구하라고 했으므로

array[0] , array[1]중 큰 값을 d[1]으로 설정해준다.

이제 d[2]부터 배열의 끝까지 값을 설정해줘야 하는데.

만약 내가 i번째 창고에 위치하고 있다면 /

i번째 창고와 같이 i-2번째 창고를 강탈할 수 있고(i-1번째는 인접하므로 불가능함)

/ i번째 창고를 강탈하지 않는다면 i-1번째 창고만을 강탈할 수 있다

첫번째는 d[i] = d[i-2] + array[i]

두 번째는 d[i] = d[i-1] 

 

이 두 값중 최댓값을 d[i]로 결정해주는 방식을 이용하여 bottom-up 방식으로 구현해주는 문제

 

이 아이디어만 생각해낸다면 코드는 정말 금방 짠다.

다이나믹 프로그래밍에서의 중요한 점은 큰 문제를 소문제로 divide 할 수 있는지에 대한 유무

문제를 많이 접해보는 것이 중요하다고 느꼈다.