[Baekjoon] 2156번 : 포도주 시식

실버 1

2156번: 포도주 시식

 

문제 풀이

이전 계단 오르기 문제와 비슷했다. 

2022.01.20 - [Algorithm/Problem] - [Baekjoon] 2579번 : 계단 오르기

 

n 번째 와인을 먹는 경우는 한 칸 전의 와인을 먹는 경우(1)와 두칸 전의 와인을 먹는 경우(2)로 나뉜다. 

(1)번 경우는 n-3 와인까지의 최대 양에 n-1번째 와인의 양과 n번째 와인의 양을 더한 것이다.

(2)번 경우는 n-2 와인까지의 최대 양에 n 번째 와인의 양을 더한 것이다.

 

여기까지는 계단 문제와 동일한 풀이이다. 

이 문제에서는 추가로 마지막 와인을 안먹을 수 있기 때문에 n번째 와인을 안먹고 n-1번째 와인까지의 최대양도 비교해준다. 

 

이 세가지 경우의 최대값을 n번째 최대 양으로 넣어주면 된다.

 

코드

# 포도주 마시기
n = int(input())
wine = []
for _ in range(n):
    wine.append(int(input()))

score = [0] * (n + 1)
score[1] = wine[0]
if n >= 2:
    score[2] = wine[0] + wine[1]

for i in range(3, n+1):
    a = score[i-2] + wine[i-1] # 2칸 띄고 현재 와인을 먹는 경우
    b = score[i-3] + wine[i-2] + wine[i-1] # 전전전 와인 + 이전 와인 + 현재 와인으로 먹는 경우
    c = score[i-1] # 이전 와인까지의 최대값
    score[i] = max(a, b, c)

print(max(score))