[백준] 2156번(python 파이썬)

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

 

*연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

처음에는 계단오르기와 같은 방식으로 풀었지만 계단오르기는 1칸 뛰어서 올라갈수 있는데 이문제는 몇칸이든 뛰어서 시음을 할 수있다.

 

이는 n잔 주워졌을떄 n-1잔 뛰어서 시음을 할 수 있다. 때문에 배열을 n+1 x n 개 만들어서 풀었지만 메모리 초과가 나왔다. 메모리 제한이 128MB이다 입력 제한이 10000인데 10001 x 10000 개 만들어버리면 당연히 메모리 초과가 나온다.

 

다시 생각했을때 최대 2잔까지 건너뛰어서 마셔도 최대값을 구할수 있다고 생각했다.

 

6

1000 1000 1 1 1000 1000

이렇게 있을때 1, 2, 5, 6을 마시는게 최대값이다.

 

7

1000 1000 1 1 1 1000 1000

이렇게 있다면 1, 2, 4, 6, 7을 마시는게 최대값이다. 3칸 뛰어 마실바에 중간에 하나를 마시는게 최대값이다.

 

n = int(input())
cost = [0]
dp = [[0] * 3 for _ in range(n + 1)]

for i in range(1, n + 1):
    cost.append(int(input()))

for i in range(3):
    dp[1][i] = cost[1]

def grape():
    for i in range(2, n + 1):
        for j in range(3):
            if j == 0:
                temp = 0
                for k in range(1, 3):
                    temp = max(temp, dp[i - 1][k])
                dp[i][j] = temp + cost[i]
            elif j == 1:
                dp[i][j] = max(dp[i - 2]) + cost[i]
            else:
                if i >= j + 1:
                    dp[i][j] = max(dp[i - (j + 1)]) + cost[i]


grape()
result = 0
for i in range(n + 1):
    result = max(result, max(dp[i]))

print(result)