728x90
2156. 포도주 시식
난이도 : 실버 1
소요 시간 : 15분
날짜 : 2025.01.05
언어 : 파이
알고리즘 유형 : dp
설명 보기전에 문제 풀어보러 가기
1. 문제 설명
- 포도주를 선택하면 모두 마셔야 하고, 제자리에 놓아야 한다.
- 연속으로 3잔을 마실 수 없다.
- 마실 수 있는 포도주 양의 최댓값을 구하기
2. 해결 방식
- dp 사용 : dp[i][j] = i번 포도주를 j잔째 마시고 있는 경우 포도주양의 최댓값.
- 0잔, 즉 i번 포도주를 안먹는다면, dp[i-1]의 값들 중 최댓값이 dp값이다.
- i번 포도주가 연속된 첫번째 잔이라면, dp[i-1][0]의 값과 dp[i-2]값들 중 최댓값에 현재 포도주 양을 더한 값이 dp 값이다.
- 두번째 잔인 경우, dp[i -1][1]의 값에 현재 포도주 양을 더해주면 된다.
3. 정답 코드
import sys
input = sys.stdin.readline
n = int(input())
dp = [[0, 0, 0] for _ in range(n)]
for i in range(n):
now = int(input())
if i == 0:
dp[i] = [0, now, now]
continue
if i == 1:
dp[i] = [dp[0][1], now, now + dp[0][1]]
continue
dp[i][0] = max(dp[i - 1])
dp[i][1] = now + max(dp[i - 1][0], max(dp[i - 2]))
dp[i][2] = now + dp[i - 1][1]
print(max(dp[-1]))
반응형
'백준 문제풀이 코드저장소 > Silver' 카테고리의 다른 글
Baekjoon 2503. 숫자 야구 / Python, Java (0) | 2024.07.12 |
---|---|
Baekjoon 4307. 개미 / Java (0) | 2024.07.07 |
Baekjoon 11478. 서로 다른 문자열의 개수 / Java (0) | 2024.07.03 |
Baekjoon 16951. 블록 놀이 / Java (0) | 2024.07.03 |