[백준/python] 2156번 포도주시식

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

2156번: 포도주 시식

문제설명

[dp]

일렬로 나열된 숫자 중 특정한 조건에 맞게 숫자의 최대 합을 구해야 하는 문제다.

(특정한 조건: 연속된 세 수는 취할 수 없음 - 두 수를 연속으로 취했다면, 그 다음 수는 취할 수 없음)

 

코드

# 21735
input=__import__('sys').stdin.readline
n=int(input())
li=[]
for i in range(n):
    li.append(int(input()))

if n == 1:
    print(li[0])
elif n == 2:
    print(li[0]+li[1])
elif n == 3:
    print(max(li[0]+li[1], li[1]+li[2], li[0]+li[2]))
else:
    dp = [li[0], li[0] + li[1], max(li[0] + li[1], li[1] + li[2], li[0] + li[2])]
    for i in range(3, len(li)):
        dp.append(max(dp[i-3]+li[i-1]+li[i], dp[i-2]+li[i], dp[i-1]))
    print(dp[-1])

 

문제풀이

우선, n이 1, 2, 3일 경우의 최대값을 기본적으로 세팅해놔야, 그 이후의 값을 점화식으로 적용할 수 있다.

n이 1, 2, 3일 때의 최대 합을 dp 리스트에 넣고, n == 4일 때부터 새로운 dp값을 넣어준다.

점화식이 떠오르지 않아서, 직접 예제 리스트로 dp값을 구해가며 점화식을 끼워 맞췄다. (ㅠㅠ)

그래서 처음에는 max(dp[i-3]+li[i-1]+li[i]와 dp[i-2]+li[i]) 값을 새로운 dp값으로 리스트에 넣어줬다.

하지만 현재의 값인 li[i]을 취하지 않는 방법도 있기 때문에, dp[i-1]을 max 함수에 추가로 넣어줘야 한다.

(이전의 방법으로 했을 땐 max(dp)를 출력하는 방식으로해서 예제 입력은 통과했지만, dp 리스트 자체가 앞선 수들의 최대 합을 계속 누적시키는 것이므로 계속해서 최대값을 유지시켜야만 리스트가 긴 다른 예제에서도 문제가 생기지 않을 것이다.)

그렇기 때문에, 가장 뒤의 값인 dp[-1]가 최대값이 된다.

dp 언젠간 익숙해졌으면 좋겠다 🫠