백준 - 포도주 시식(2156번) - 배열 내에서 조건에 맞는 최대값 찾기(DP)

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

이러한 유형의 문제는 가능한 조건을 미리 정리해놓고 풀이하는게 더 좋은 방법인것 같다.

특히 첫번째 부터 규칙을 찾으려고 하면 번거롭기 때문에 적당히 i값을 0이 아닌 4,5 정도의 값을 설정하고(규칙에 따라 유동적으로) 앞의 원소들을 체크하면서 풀이해야한다.

 

 위 문제의 조건을 바탕으로 가능한 경우는 3가지가 있다.

 

1. i 번째 포도주를 마시면서 i-2번째 포도주까지 마셔온 경우 (arr[i] + dp[i-2])

2. i 번째 포도주와 i-1번째 포도주를 마시고 i-3번째 포도주 까지 마셔온 경우 (arr[i] + arr[i-1] + dp[i-3])

3. i 번째를 스킵한 경우 즉, i-1,i-2번째 포도주를 연속해서 마신 경우 (dp[i-1])

 

이 세가지 경우의 최대값이 dp[i]가 된다.

 

import sys

N=int(sys.stdin.readline())
arr=[]
dp=[0]*N
for _  in range(N):
    arr.append(int(sys.stdin.readline()))
dp[0]=arr[0]
if N>1:
    dp[1]=arr[0]+arr[1]
if N>2:
    dp[2]=max(dp[1],arr[0]+arr[2],arr[1]+arr[2]) 
    for i in range(3,N):
        dp[i]=max(arr[i]+dp[i-2],arr[i-1]+arr[i]+dp[i-3],dp[i-1])
print(dp[-1])