https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
문제 해결을 위한 과정
이 문제 역시 전형적인 dp로 해결할 수 있는 문제였습니다. 계단 오르기 문제(https://www.acmicpc.net/problem/2579)와 거의 유사하였으나 계단 오르기 문제는 꼭 마지막을 밟아야 한다는 조건이 있었던 반면 이 문제의 경우는 마지막 포도주를 꼭 먹어야 한다는 조건이 존재하지 않습니다. 따라서 max 조건에서 data[i] + dp[i-2], data[i] + data[i-1] + dp[i-3]과 함께 dp[i-1] 조건 역시 비교해야 합니다. 따라서 이를 소스코드로 작성하면 다음과 같습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
n = int(input())
data = [0] * 10001
dp = [0] * 10001
for i in range(n):
data[i] = int(input())
dp[0] = data[0]
dp[1] = data[0] + data[1]
dp[2] = max(data[0] + data[1], data[0] + data[2], data[1]+ data[2])
for i in range(3, n):
dp[i] = max(data[i] + dp[i-2], data[i] + data[i-1] + dp[i-3], dp[i-1])
print(max(dp))
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 9251번: LCS(Python) (0) | 2022.01.29 |
|---|---|
| 백준 알고리즘 1904번: 01타일(Python) (0) | 2022.01.28 |
| 백준 알고리즘 1912번: 연속합(Python) (0) | 2022.01.25 |
| 백준 알고리즘 1149번: RGB거리(Python) (0) | 2022.01.24 |
| 백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열(Python) (0) | 2022.01.20 |