문제 설명
•
연속된 세 잔을 마실 수 없을 때, 최대한 많은 포도주를 마시는 방법을 구하는 문제
예제 입력/출력
•
입력1
6
6
10
13
9
8
1
Plain Text
복사
•
출력1
33
Plain Text
복사
제약 조건
•
•
포도주의 양
문제 풀이
•
연속된 세 잔을 모두 마실 수 없다는 조건을 잘 고려해서 DP 관계식을 세우면 된다.
•
DP 테이블 설계
◦
: i번째 잔까지 고려했을 때 마실 수 있는 최대 포도주의 양
•
DP 관계식
◦
각 잔을 마실지, 마시지 않을지를 고려해야 하므로, 다음 세 가지 선택지 중 최적해를 찾는다.
◦
Case 1 i번째 잔을 마시지 않는다.
▪
그냥 안 마시는 경우
▪
dp[i-1]
◦
Case 2 i번째 잔을 마시고, (i-1)번째 잔은 마시지 않는다.
▪
i-1번째 잔을 건너뛰고 i번째 잔을 마시는 경우
▪
dp[i-2] + wines[i]
◦
Case 3 i번째 잔을 마시고, (i-1)번째 잔도 마신다.
▪
번째 잔과 번째 잔을 연속으로 마시는 케이스
▪
번째 잔은 마시면 안 되므로, 번째까지의 최적해를 가져와야 한다.
▪
dp[i-3] + wines[i-1] + wines[i]
•
초기값 처리
◦
관계식을 보면 dp[i]을 완성할 때 dp[i-1]부터 dp[i-3]까지 접근한다.
◦
따라서, 초기값 설정을 다음과 같이 해준다.
▪
▪
▪
풀이 코드
•
DP -
import sys
input = lambda: sys.stdin.readline()
def max_wine(n, wines):
if n == 1:
return wines[1]
# DP 테이블 초기화
dp = [0] * (n + 1)
dp[1] = wines[1]
dp[2] = max(dp[1], wines[0] + wines[2], wines[1] + wines[2])
# 점화식 적용
for i in range(3, n + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + wines[i], dp[i - 3] + wines[i - 1] + wines[i])
return dp[n]
# 입력 값 받기
n = int(input())
wines = [0] + [int(input()) for _ in range(n)] # 1-index
# 결과 출력
print(max_wine(n, wines))
Python
복사