伯準-2579(Python)-階段を登る
5414 ワード
階段を登る
質問する
階段を登るゲームは階段の下の起点から階段の先端の終点までのゲームです.図1>に示すように、階段ごとに一定の点数が書かれており、階段を踏むと階段の点数が得られます.
<図2>に示すように、始点から、第1、2、4、6段の階段を歩いて終点に着き、合計10+20+25+20=75点となる.
階段を登るには以下のルールがあります.
階段は一度に1段または2段上がることができます.つまり、階段に沿って、次の階段を上ったり、次の階段を下りたりすることができます.
連続した3つの階段を踏んではいけない.しかし、起点は階段には含まれていません.
最後に着いた階段は必ず踏まなければなりません.
そのため、最初の階段に沿って、2番目か3番目の階段を歩くことができます.しかし、最初の階段を踏んで4番目の階段を登ったり、最初の階段、2番目の階段、3番目の階段を連続して踏んだりすることはできません.
各段階の点数を与える場合は、ゲームの総点数の最値を求めるプログラムを作成します.
入力
入力した最初の行には、階段の数が表示されます.
2行目から、1行1つ、一番下の階段から、各階段に書いてある点数を順番にあげます.階段の個数は300以下の自然数で、階段に書いてある点数は10000以下の自然数です.
しゅつりょく
1行目に階段を登るゲームで得られる総得点の最値を出力します.
コード#コード#
解法
階段を上るときは、これからどうやって上がるか考えず、どこから上がるか考えます.
問題の条件の下で、連続して3格に上がることができません.
自己位置点数+1格以下の点数+3格以下の最大点数(DP)
自分の位置点数+2格以下の点数より大きい値をDPリストに保存します.
先に比較したように、連続して3コマ上昇することは避けられます.
に答える
N = int(input())
stair = [0]
for _ in range(N):
stair.append(int(input()))
if N == 1:
print(stair[1])
else:
dp = [0] * (N+1)
dp[1] = stair[1]
dp[2] = stair[1] + stair[2]
for i in range(3, N+1):
dp[i] = max(dp[i-3]+stair[i-1]+stair[i], dp[i-2]+stair[i])
print(dp[N])
Reference
この問題について(伯準-2579(Python)-階段を登る), 我々は、より多くの情報をここで見つけました https://velog.io/@junyp1/백준-2579-Python-계단-오르기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol