[백준] 2156번 포도주 시식(다이나믹 프로그래밍)(DP)(Python - 파이썬)

백준 2156번 문제입니다. (solved.ac)기준 실버 1 문제입니다.

아래에 있는 백준 2579번 계단 오르기 문제와 굉장히 유사한 문제입니다.

[백준] 2579번 계단 오르기(다이나믹 프로그래밍)(DP)(Python)

[백준] 2579번 계단 오르기(다이나믹 프로그래밍)(DP)(Python)

문제 접근

포도주를 마시는데에는 두 가지 규칙이 존재합니다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.

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

동적계획법(다이나믹 프로그래밍)으로 접근하였고 

wine 이라는 리스트를 만들어 wine[n]에는  n번째 포도주 잔에 있는 포도주 양을 담도록 하고

d라는 리스트를 만들어 d[n]에는 n번째 포도주를 먹거나 먹지 않을 때 최대 포도주의 양이 들어갑니다.

 d[n]에서 n번째 포도주를 먹을 경우 최대 포도주의 양은 아래 두 경우 중 더 큰 값이 됩니다. (연속으로 3잔을 마실 수 없음)

# n번째 전전전의 위치까지 마실 수 있는 포도주양의 최댓값(d[n-3]) + n번째 전에 있는 포도주의 양(wine[i-1]) + 
# n번째에 있는 포도주의 양(wine[n])
d[n-3] + wine[n-1] + wine[n]

# n번째 전전의 위치까지 마실 수 있는 포도주양의 최댓값(d[n-2]) + n번째에 있는 포도주의 양(wine[n])
d[n-2] + wine[n]

d[n]에서 n번째 포도주를 먹지 않을 경우 아래와 같이 d[n-1]이 최대 포도주의 양이 됩니다.

# n번째 전의 위치까지 마실 수 있는 포도주 양의 최댓값(d[n-1])
d[n-1]

따라서 d[n]의 값은 위의 3가지 경우중 최댓값이 됩니다.

    d[n] = max(d[n-3] + wine[n-1] + wine[n], d[n-2] + wine[n], d[n-1])

 

만약 d[n]을 구할 때 n번째 포도주를 마시지 않을 경우를 고려하지 않는다면 예제 1번 기준으로 

d리스트에는 [0, 6, 16, 23, 33, 32]가 들어가게 됩니다. 

n번째 포도주를 마실 경우를 고려한다면 

d리스트에 [0, 6, 16, 23, 28, 33, 33]가 들어가게 됩니다.

 

잘 이해가 되시지 않는다면 백준 질문글 중 자세한 답변을 해주신 분이 계셔서 링크를 첨부해 두겠습니다.

https://www.acmicpc.net/board/view/60664

정답 코드

n = int(input())

# 인덱스 관리가 쉽도록 맨앞을 0으로 wine[0] = 0
# 따라서 첫번째 포도주의 양은 wine[1]
wine =[0]
d = [0] * (n+1)

for _ in range(n) :
    wine.append(int(input()))

d[1] = wine[1]
if n >= 2 :
    d[2] = wine[1] + wine[2]

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

print(d[n])