[파이썬] 백준 2156 : 포도주 시식 (실버1)

[파이썬] 백준 2156 : 포도주 시식 (실버1)

 

2156번: 포도주 시식

---

문제

---

풀이

방향성 생각

arr에 포도주를 순서대로 넣는다.

상태는 3가지가 존재한다.

선택하지 않은 상태 /  연달아 1개를 선택한 상태 / 연달아 2개를 선택한 상태.

 

dp 배열을 3xn으로 만든다. 

DP 배열의 시작은 각각 0, arr[0], 0으로 초기화한다.

배열의 첫번째에는 이전에 선택하지 않거나 연달아 두 개 선택한 경우는 없음.

dp[0][i+1] : 현재 포도주를 선택하지 않는 경우 -> 연달아서 선택하지 않거나, 한 개를 선택 후 선택하지 않거나, 두 개를 선택 후 선택하지 않는 경우 중 가장 큰 경우를 선택한다.

dp[1][i+1] : 이전 것을 선택하지 않고 현재 포도주를 선택한 경우이다.

dp[2][i+1] : 이전 것을 선택하고 연달아서 현재 것을 선택한 경우이다.

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

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

dp = [[0]*n for i in range(3)]
dp[1][0] = arr[0]

for i in range(n-1):
    dp[0][i+1] += max(dp[2][i],dp[1][i],dp[0][i])
    dp[1][i+1] += dp[0][i]+arr[i+1]
    dp[2][i+1] += dp[1][i]+arr[i+1]
    
print(max(dp[0][-1],dp[1][-1],dp[2][-1]))

 

import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
arr = [int(input()) for _ in range(n)]

dp = [[0]*n for _ in range(3)]
dp[1][0] = arr[0]

for stage in range(n-1):
    dp[0][stage+1] += max(dp[state][stage] for state in range(3))
    for i in range(2):
	    dp[i+1][stage+1] += dp[i][stage] + arr[stage+1]

print(max(dp[state][-1] for state in range(3)))

다시 풀어본 풀이

코멘트

단순 일차원적으로 접근해서 점화식 세워서 풀려면 머리 아플 수 있는데 '상태'에 집중해서 구분할 수 있는 배열을 만들어서 풀면 어렵지 않다.