포도주 시식 (BOJ-2156)

in ALGORITHM

‘시간제한 2초, 메모리제한 128MB, BOJ-2156’

포도주 시식 (BOJ-2156)
DP를 활용하여 해결해야 한다. 뒤에서부터 포도주를 마실 경우 다음과 같이 볼 수 있다.

DP Solving

  1. 뒤에서 4번째 잔 까지 마신 양 dp(i-3) + 뒤에서 두번째 잔을 마신 양 li(i-1) + 마지막 잔 <뒤에서 첫번째=""> li(i)
  2. 뒤에서 3번째 잔 까지 마신 양 dp(i-2) + 마지막 잔 li(i)
  3. 뒤에서 2번째 잔 까지 마신 양 dp(i-1)

이 셋 중에서 가장 큰 걸 dp로 저장하면 된다.
이 문제는 뒤에서부터 포도주를 마시는걸 떠올리면 dp로 구현하는게 좀 더 수월해진다.

n = int(input())

li = [0]
dp = [0] * (n + 1)
for i in range(n):
    li.append(int(input()))

if n == 1:
    print(li[1])

elif n == 2:
    print(li[1] + li[2])

else:
    dp[1] = li[1]
    dp[2] = li[1] + li[2]

    for i in range(3, n + 1):
        dp[i] = max(dp[i - 3] + li[i - 1] + li[i], dp[i - 1], dp[i - 2] + li[i])

    print(dp[n])