티스토리 뷰
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
n = int(input())
d=[0]*n
array=[]
for _ in range(n):
array.append(int(input()))
for i in range(n):
if i==0:
d[0]=array[0]
elif i==1:
d[1]=d[0]+array[1]
elif i==2:
d[2]=max(array[0], array[1])+array[2]
else:
d[i]=max(max(d[:i-2])+array[i-1], max(d[:i-1]))+array[i]
print(max(d))
|
cs |
넘넘 어렵게 풀었다..
i 번째 포도주를 먹을 때, max(i-1번째를 먹고+i-3번째를 먹었을 때 최댓값 vs i-2번째 먹었을 때 최댓값)이렇게 초기에 식을 세웠는데, 틀려서 반례를 돌려봐서 다시 체크해보았다. 고친 부분은 저 초록색 친 부분이 i-3번째 이하, i-2번째 이하 최댓값들 중 최댓값을 고르는 방식으로 바뀐 점이다. 그런데. 다른분 풀이 보니깐 이렇게 복잡하게 할 필요 없고 마찬가지로 최종 결과값을 반환할 때 max(d) 를 하지 않아도 d[n-1]만 해도 나오는 점화식을 보게 되었다.
BOJ 2156 · 포도주 시식
알고리즘 분류 : 다이나믹 프로그래밍 N개의 포도주 잔이 있을 때, 최대로 마실 수 있는 포도주의 양을 구해야 한다. DP를 이용하여 포도주 마시는 규칙에 따라 구현하면 된다. 포도주는 연속으
rebas.kr
d[i]를 3가지로 분류해서 점화식을 세우는데 이때 나머지 2가지는 내가 한 방식과 같고 남은 1가지는 i 번째 포도주를 마시지 않고 건너뛰고 d[i]=d[i-1] 해주는 경우이다.
이렇게 마시지 않는 경우도 추가하면 위의 문제 상황들을 해결할 수 있다.
'Problem Solving' 카테고리의 다른 글
| [BOJ 3190] 뱀 (Python3) (0) | 2021.02.24 |
|---|---|
| [BOJ 3079] 입국심사 (Python3) (0) | 2021.02.24 |
| [BOJ 9465] 스티커 (Python3) (0) | 2021.02.22 |
| [BOJ 1912] 연속합 (Python3) (0) | 2021.02.22 |
| [BOJ 9019] DSLR (Python3) (0) | 2021.02.22 |