[Python] 2156번 포도주 시식, 그림 설명, 자세한 설명, 완벽 분석

✏️ 문제

 

문제 파악

2579번 계단 오르기 와 유사한 문제이다!

저 문제와의 차이점은 계단 오르기는 꼭 마지막 계단을 밟아야 하는데 이 문제는 꼭 마셔야 하는 포도주가 없다는 것이다.

 

그러면 경우의 수를 나누면 다음과 같이 나온다.

• n번째 포도주를 마신다.
  • n-2번째 포도주를 마셨다.
  • n-3번째 포도주와 n-1번째 포도주를 마셨다.
• n번째 포도주를 마시지 않는다.
  • n-2번째 포도주와 n-1번째 포도주를 마셨다.

나는 다른 풀이들이 다 해당 포도주를 마시지 않는다는 조건을 두길래 왜 최대를 구하는데 마시지 않는 조건을 고려하는 거지? 라고 생각했는데 이유를 생각해보니 다음과 같았다. 

해당 포도주를 마시지 않는다는 조건을 두는 이유는

1. n번째 포도주를 마시지 않고 n-2번째 포도주와 n-1번째 포도주를 마셨을 때 최대일 경우도 있기 때문이다.
2. 무조건 n번째 포도주를 마시라는 말이 없기 때문이다.

이해하기 좋은 예시로 

6
100
100
0
0
100
100

 

이 있다.

위의 예시에서는 3번째와 4번째일 때 해당 포도주를 안마시고 5번째일 때 연속으로 포도주를 마시는 게 최대로 마실 수 있다.

 

그림으로 작성하면 다음과 같다.

초록색이 n-2번째까지 최대로 마신 포도주의 양 + n번째 포도주를 마신 경우이다.

보라색이 n-3번째까지 최대로 마신 포도주의 양 + n-1번째 포도주 + n번째 포도주를 마신 경우이다.

파란색이 n-1번째까지 최대로 마신 포도주의 양 + n번째 포도주를 마시지 않은 경우이다.

 

 

알고리즘

• 다이나믹 프로그래밍 

 

코드

n = int(input())
grape = [0] 
for _ in range(n):
  grape.append(int(input()))

dp = [0] * (n+1)
dp[1] = grape[1]

if n > 1: 
  dp[2] = grape[1] + grape[2]

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

print(dp[n])