반응형
https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
n = int(input())
wine = [0] + [int(input()) for _ in range(n)]
dp = [0] * (n+1)
if n == 1:
print(wine[1])
else:
dp[1] = wine[1]
dp[2] = wine[1] + wine[2]
# 최대로 마실 수 있는 포도주의 양 구하기
for i in range(3, n+1):
dp[i] = max(dp[i-1], dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i])
print(max(dp))1. 포도주 번호가 1-n까지이기 때문에 인덱스를 맞춰주기 위해 wine, dp를 n+1 길이로 생성한다.
2. n == 1 인 경우 바로 값을 출력한다.
3. n != 1 인 경우 최대로 마실 수 있는 포도주의 양을 구한다. 포도주를 마시는 경우를 나눠서 최대를 구한다.
3-1. dp[i-1] = 해당 포도주를 마시지 않는 경우
3-2. dp[i-2] + wine[i] = 해당 포도주를 마시고 이전 포도주를 마시지 않는 경우
3-3. dp[i-3] + wine[i-1] + wine[i] = 해당 포도주를 마시고 이전 포도주도 마시는 경우
4. dp의 최대값을 출력한다.
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준/Python] 결혼식 (0) | 2021.11.12 |
|---|---|
| [백준/Python] 1로 만들기 (0) | 2021.11.10 |
| [백준/Python] 회전하는 큐 (0) | 2021.11.03 |
| [백준/Python] 시리얼 번호 (0) | 2021.10.31 |
| [백준/Python] 절대값 힙 (0) | 2021.10.23 |