[백준] 2156 파이썬(python) : 포도주 시식 - (★)

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

2156번: 포도주 시식

 

 

import sys
n = int(sys.stdin.readline())
dp = [0]*10001
glass = [0]*10001
for i in range(1, n+1):
    glass[i] = int(sys.stdin.readline())
dp[1] = glass[1] #1
dp[2] = glass[1] + glass[2] #2
for i in range(3, n+1): #3
    dp[i] = max(dp[i-1], dp[i-2]+glass[i], dp[i-3]+glass[i-1]+glass[i]) #4
print(dp[n])

 

#1 : dp[1]은 첫번째 포도주의 양이니까 glass[1]

#2 : dp[2]는 두번째까지의 포도주의 양이니까 glass[1] + glass[2]

#3 : 연속으로 3잔 이상 마실 수 없으니까 3부터 시작, dp의 인덱스를 1부터 시작했으므로 n+1까지 반복

#4 : dp[i-1]은 i이전까지의 모든 포도주를 다 포함하니까 하나만 존재(i번째는 glass는 3번 연속에 걸리기 때문에 pass), d[i-2] + glass[i]는 i-2까지의 최대 포도주 마실 수 있는 양 + i-1을 건너뛴 glass[i]의 양, dp[i-3] + glass[i-1] + glass[i]는 i-3까지의 포도주의 양 + i-2를 건너뛴 glass[i-1] + glass[i]를 의미한다.

 

마지막 dp[n]을 구하면 그때까지의 최대값 포도주의 양을 구할 수 있다.(dp를 인덱스 1부터 시작했으므로 dp[n]을 출력)

 

2579번 : 계단 오르기는 dp의 인덱스를 0부터 시작해서 반복문을 n까지하고 마지막 출력도 dp[n-1]을 했는데 이 문제의 풀이와 다르다.

그냥 이렇게 푸는거다 하고 받아드리면 편하다. 개기면 힘들다

 

---

2579번 : 계단 오르기