[BOJ] [Python] 2156번 : 포도주 시식

3잔 연속 마실 수 없다는 조건을 고려하여 점화식을 세워야 한다.

 

조건을 고려하면, 4번째 잔부터 점화식이 적용된다.

따라서 1~3번째 잔까지는 적절히 초깃값을 넣어준다.

 

점화식을 살펴보자.

 

 

처음에 생각한 규칙

 

 

현재 마셔야 하는 컵 기준, 최고의 선택을 해야 한다.

 

3잔 연속으로 안 마시기 위한 선택권은 2개이다.

 

1. 3번째 앞의 컵 DP + 1번째 앞의 컵 값 + 현재 컵

2. 2번째 앞의 컵 DP

 

 

 

 

 

"틀렸습니다"

 

아래 코드는 틀린 코드이다.

완벽하다고 생각했는데, 틀렸다. 왜 틀렸을까?

 

num = int(input())

li = []

for _ in range(num):
    li.append(int(input()))


dp = [0] * num

for i in range(0, num):
    if i == 0:
        dp[0] = li[0]

    elif i == 1:
        dp[1] = li[0] + li[1]

    elif i == 2:
        dp[2] = max(li[0], li[1]) + li[2]

    else:
        dp[i] = max(li[i - 1] + dp[i - 3], dp[i - 2]) + li[i]

print(max(dp))

 

 

 

몇 가지 예시를 생각해보다가, 반례를 찾았다.

 

반례

 

사진에서 알 수 있듯이, 0 10 5 10 1 10을 마시면 36을 마실 수 있다.

 

하지만 내 방법대로 한다면, 0 10 5 10 0 10으로 35를 마시게 된다.

 

맞다. 5 10 0 0 1 10 구간이 문제가 되는 것이다.

두 잔을 건너뛸 수 있는 상황을 만들어줘야 이 문제가 해결된다.

 

 

따라서 규칙을 하나 더 만들었다.

 

최종 규칙

 

1번 규칙이 새로 생긴 규칙이다.

 

 

"맞았습니다"

 

num = int(input())

li = []

for _ in range(num):
    li.append(int(input()))


dp = [0] * num

for i in range(0, num):
    if i == 0:
        dp[0] = li[0]

    elif i == 1:
        dp[1] = li[0] + li[1]

    elif i == 2:
        dp[2] = max(li[0], li[1]) + li[2]

    elif i == 3:
        dp[i] = max(li[i - 1] + dp[i - 3], dp[i - 2]) + li[i]

    else:
        dp[i] = max(li[i - 1] + dp[i - 3], dp[i - 2], li[i - 1] + dp[i - 4]) + li[i]


# print(dp)
print(max(dp))