[BOJ 156]ワイン試飲(Python)

質問する

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

これはワインを最大限に飲む問題です.うらやましい🙃
このとき3杯続けて飲むことができないことを考える必要があります.

問題を解く

ブドウの酒量を記録したdistリストを作成した.
dist[i]は、iの最初の位置に来たとき、最も多くのワインを飲んだ量を記録しています.
言葉で説明するより絵で見た方が分かりやすいようなのでやってみました.
iの最初のインデックスでは、3つのケースを考慮する必要があります.
1. wine[i] + wine[i-1] + dist[i-3]
2. wine[i] + dist[i-2]
3. dist[i-1]

🔥 3格の法則を守って、最も多くの格のワインを飲むと必ずしも最高の効果が得られるとは限らない.
例:
4番目の格のワインを飲んで、3番目の格を続けて、6番目の格のワインを飲むことができません.

したがって、dist[i]に入れた最値を比較する際には、dist[i-1]を考慮しなければならない.

dist[i] = max(wines[i] + wines[i-1] + dist[i-3], 
              wines[i] + dist[i-2],
              dist[i-1])

コード#コード#

import sys
input = sys.stdin.readline
INF = sys.maxsize

n = int(input().rstrip())
wines = [0] * (n+1)
dist = [0] * (n+1)

for i in range(1,n+1):
    wines[i] = int(input().rstrip())

if n==1:
    print(wines[1])
    sys.exit(0)
elif n==2:
    print(wines[1]+wines[2])
    sys.exit(0)
else:
    dist[1] = wines[1]
    dist[2] = wines[1] + wines[2]
    dist[3] = max(wines[1] + wines[3], wines[2] + wines[3], dist[2])

    for i in range(4,n+1):
        # dist[i] = wines[i] + max(wines[i-1] + dist[i-3], 
        #                         wines[i-2] + dist[i-3])
        dist[i] = max(wines[i] + wines[i-1] + dist[i-3], 
                      wines[i] + dist[i-2],
                      dist[i-1])

    print(dist[n])