백준 - 2156번

import sys

n = int(sys.stdin.readline())
wine = [0] * n

for i in range(n):
    wine[i] = int(sys.stdin.readline())


arr = [0] * (n-1)



for i in range(n-1):
    arr[i] = (int(wine[i]) + int(wine[i+1]))

temp = [0] * 10001

t = 0
for i in range(len(arr)):
    for k in range(len(arr)):
        t = t+1
        try:
            temp[t] = (arr[i] + arr[i + k + 3])
        except IndexError:
            pass

k = max(temp)

print(k)

시간 초과라고 뜨지만 답도 틀린 것 같다.

 

 

import sys

n = int(sys.stdin.readline())
wine = [0]

for i in range(n):
    wine.append(int(sys.stdin.readline()))


dp = [0]
dp.append(wine[1])

if n>1:
    dp.append(wine[1] + wine[2])

for i in range(3,n+1):
    dp.append(max(int(dp[i-2]) + int(wine[i]), int(dp[i-3]) + int(wine[i-1]) + int(wine[i]),
                  int(dp[i-1])))

print(max(dp))

다이나믹 프로그래밍을 하는 생각 구조는 이렇게 하면 될 것 같다.

1. 문제의 규칙을 '최대한 간단한 조건' 일때 찾는다.

2. dp[0] = 0으로 비워두자

3. 1번과 2번의 케이스는 하드코딩을 통해서 직접 만들어 놓는다.

4. 보통 3번째 부터 시작하는 것이 좋다.

5. 이전값을 dp에 저장하고 호출하는 방식으로 규칙을 짜야한다.