Baekjoon 2156 포도주 시식

Baekjoon 2156 포도주 시식 

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

동적 계획법에 해당하는 본 문제는 문제를 잘개 쪼개서 생각하는 것이 중요하다

이 블로그에서는 올리지 않았지만 2579번 계단 오르기 문제와 매우 비슷하다.

혹시 풀어보지 않았다면 찾아보길 바란다.

이와 같은 문제 해결에 실마리가 될 것이다.

Solution

Key는 바로 연속으로 3잔을 마실 수 없다는 점이다.

그렇다면 우리는 어떻게 설정해야할까 고민을 해보자

우선 i 번째를 마신다고 가정한다면

i번째	i-1 번째	i-2 번째
⚪	⚪	╳
⚪	╳	⚪
╳	⚪	⚪

다음과 같이 생각할 수 있다.

우리가 고려해야하는 상황은 i 번째일 때 위와 같은 3가지가 존재하는 것을 인지한 후

첫 스타트를 어떻게 끊을까를 생각해야한다.

사람마다 해결하는 방법은 다양하겠지만 대체로 비슷하다.

방법 1

n = int(input())
a = [0]
for i in range(n):
    a.append(int(input()))

tmp = []
tmp.append(a[0])
tmp.append(a[1])
if len(a) > 2:
    tmp.append(a[1]+a[2])
for i in range(3,n+1):
    tmp.append(max(a[i]+tmp[i-2],a[i]+a[i-1]+tmp[i-3], tmp[i-1]))

print(max(tmp))

방법 1의 경우는 a list 숫자와 집어넣는 숫자의 일치성을 위해 0을 집어넣고 n개의 숫자를 집어 넣어 1번째 숫자와 a[1]이 일치하도록 만들었고
첫 번째와 두 번째의 경우까지는 손수 만든 후 3번째 숫자부터 위에서 설명한 임의의 i 번째를 해결하도록 loop를 만들었다.



방법 2 - 숏코딩 대표

import sys;I=sys.stdin.readline;w=[0]*3
for i in range(int(I())):p=int(I());w=w[1]+p,w[2]+p,max(w)
print(max(w))

이 방법의 경우 달라 보이지만 크게는 같다.
왜냐하면 max(w)의 경우는 방법 1의 경우에서 tmp[i-1] 즉 ╳⚪⚪을 의미하고
w[1]+p의 경우 ⚪⚪╳
w[2]+p의 경우 ⚪╳⚪를 의미한다.

다른 방법으로 리스트 Nx3 행렬 형태로 만들어 사용하는 경우도 있으니 참조하길 바란다.

ALL RIGHT RESERVED TWINSTARINFO