09009
[백준 2156번] 포도주 시식 본문
문제 보기
https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
문제 해결
마지막 포도주를 마셨을 때랑 마시지 않았을 때를 가정하여 문제를 해결해야 한다.
i = 2
- 마지막 포도주를 마실 때
- 마지막 포도주를 마시지 않을 때
i = 3 이상일 때
- 마지막 포도주를 마실 때
- 마지막 포도주를 마시지 않을 때
소스 코드
n = int(input())
arr = [0] * 10000
for i in range(n):
arr[i] = int(input())
d = [0] * 10000
d[0] = arr[0]
d[1] = arr[0] + arr[1]
d[2] = max(arr[0] + arr[2], arr[1] + arr[2], d[1])
for i in range(3, n):
d[i] = max(d[i-3] + arr[i-1] + arr[i], d[i-2] + arr[i], d[i-1])
print(max(d))
'Algorithm > DP' 카테고리의 다른 글
| [프로그래머스 lv2] 가장 큰 정사각형 찾기 (0) | 2023.10.15 |
|---|---|
| [백준 1699번] 제곱수의 합 (0) | 2023.10.03 |
| [백준 11053번] 가장 긴 증가하는 부분 수열 (0) | 2023.09.24 |
Comments