[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])Reference
この問題について([BOJ 156]ワイン試飲(Python)), 我々は、より多くの情報をここで見つけました https://velog.io/@uoayop/BOJ-2156-포도주-시식Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol