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

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
N = int(input())
d = [0] * (N)
arr = list(map(int,sys.stdin.readline().split()))
d[0] = arr[0]
d[1] = arr[1]
for i in range(2,N):
    d[i] = max(d[i-1],d[i-2]+arr[i])

print(d[N-1])

보텀업 방식으로 풀었다

d[0],d[1]은 무조건 고정값일수밖에 없으므로... 피보나치 수열에서 초항 두개가 고정인 이유랑 같을 것 같다

 

d[2]는 d[0] + arr[2]값이겠지 싶었지만

내가 0번째 창고를 훔칠지 , 1번째 창고를 훔칠지 모르잖아요?

근데 식량이 음수는 아닐테니.. 뭐든 더해주는게 더 최댓값에 수렴할 수 있겠죠

그래서 내가 만약 현재 창고를 훔칠 거야! -> 바로 왼쪽 x , 왼쪽 왼쪽 건너편꺼까진 가져올 수 있겠죠

d[i-2] + arr[i]

 

나 이창고 안 훔칠 거야! 

그럼 d[i-1]을 가져오면 됩니다

이 창고를 안 훔친다는건 그 옆에있는것의 데이터를 복사해오면 되겠죠

 

둘중 최댓값을 구하면 됩니다(문제에서 제시)

 

DP가 처음엔 아예 이해가 안 됐었는데

두번째 보니까 뭔지는 얼추 감이 잡히네요

 

처음부터 막 코드를 짜기보단 문제를 이해하는데 시간을 아끼지 말고

구조를 먼저 파악하는것이 중요한 것 같습니다.