[Baekjoon] 2156번 : 포도주 시식 (Python)

[Baekjoon] 2156번 : 포도주 시식 (Python)

 

목차

 

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

Python

 

방법 1 - 메모리 30864KB / 시간 80ms / 코드 길이 240B

 

Baekjoon 2579번과 유사한 문제이다.

https://aigong.tistory.com/380

[Baekjoon] 2579번 : 계단 오르기 (Python)

 

다만 차이로 볼 수 있는 점은 또 다른 경우의 수인 3번째 경우가 존재한다는 것이다.

계단 오르기와 다른 큰 차이점은 굳이 2칸씩 뛰거나 1칸씩 뛸 필요가 없다는 점이다.

단순히 연속한 3개의 잔만 마시지 않으면 되고 몇 번을 건너 뛰던지 그냥 최대로 구할 수 있기만 하면 된다.

극단적인 예로

"마심, 안 마심, 안 마심, 안 마심, 안 마심, 마심" (OXXXXO)도 가능한 예이다.

 

이말인즉슨, 앞의 두 경우

1) 현재 i 번째의 값 + 2칸 떨어진 i-2의 dp 값 : l[i]+d[i-2]

2) 현재 i 번째의 값 + i-1 번째의 값 + 3칸 떨어진 i-3의 dp 값 :  l[i]+l[i-1]+d[i-3]

는 i번째 음료를 마실 때의 경우의 수이다.

다만 여기서 3번째는 그냥 현재 i 번째 마시지 않고 그 이전 dp값 : d[i-1]을 통해 최대값을 설정하는 것으로 고려할 수 있다.

 

0	6	10	13	9	8	1	1	2	4
l0	l1	l2	l3	l4	l5	l6	l7	l8	l9
l0	l1	l1+l2	d[2] l3+d[1] l3+l2+d[0]	d[3] l4+d[2] l4+l3+d[1]	d[4] l5+d[3] l5+l4+d[2]	d[5] l6+d[4] l6+l5+d[3]	d[6] l7+d[5] l7+l6+d[4]	d[7] l8+d[6] l8+l7+d[5]	d[8] l9+d[7] l9+l8+d[6]
0	6	16	23	28	33	33	34	36	39

 

참조)

https://www.acmicpc.net/board/view/60664

글 읽기 - 잘 이해가 되지 않아 이렇게 질문드립니다..ㅜㅜㅜ

 

import sys
input = sys.stdin.readline
n=int(input())
l=[0]+[int(input()) for _ in range(n)]
d=[0]*(n+1)
d[1] = l[1]
if n>1:
    d[2] = l[1]+l[2]
for i in range(3,len(d)):
    d[i] = max(l[i]+d[i-2], l[i]+l[i-1]+d[i-3], d[i-1])
print(max(d))

 

방법 2 - 메모리 30860KB / 시간 76ms / 코드 길이 155B

 

방법 1에서 이야기한 3가지 경우의 수를 잘 조합한 것이 아래의 방법이다.

 

import sys
input = sys.stdin.readline
l=[int(input()) for _ in range(int(input()))]
d=[0,l[0],0]
for i in l[1:]:
    d=[max(d),d[0]+i,d[1]+i]
print(max(d))