DP 응용문제(이코테) - 1

날짜 : 2022. . 

사용 언어 : python

 

문제

 

코드

import sys

n = int(sys.stdin.readline())
k = list(map(int, sys.stdin.readline().split()))
food = [0] * (n+1)
food[0] = k[0] # 첫번째를 고르는 경우
food[1] = k[1] # 두번째를 고르는 경우

for i in range(2, n):
    food[i] = max(food[i-2] + k[i], food[i-1]) # 세번째부터 첫번째와 두번째의 경우를 비교

print(food[n-1]) # 해당되는 값 출력

 

 

풀이

- 첫 번째 창고와 두 번째 창고의 경우 불가결한 상황이기 때문에 처음에 값을 설정

- 세 번째 창고의 경우 첫 번째와 두 번째 창고를 약탈한 이후에 도착할 수 있기 때문에 해당 케이스를 분리한 후 비교하여 저장한다.

-> 그러므로 세 번재 창고의 값은 첫 번째 창고 + 세 번째 창고와 두 번째 창고 약탈한 값 중 최댓값을 선택하여 저장한다.

- 이를 반복하여 n번째 창고까지 도달한 후 food[n-1]을 출력함으로써 문제는 해결된다.

 

 

알게된 점

- DP문제에서의 상향식, 하향식 전개방식과 메모이제이션을 능숙하게 해야 DP문제에서 승산이 보인다는 것을 체감했다.

 

 

참고 사이트

-