(DP)白駿2193号が親水
1989 ワード
s = [0, 1, 1]
for i in range(3, 91):
s.append(s[i - 2] + s[i - 1])
n = int(input())
print(s[n])
1から順に状況の数を書き出し、結果はs[i]がs[i-2]+s[i-1]であることを示した.どうしてこんな結果になったのでしょうか.
この選手の一番前の数字は1でなければならないし、1は連続できないからだ.
一番前の数字は1が固定されていて、後ろに「0」と「01」が付いている場合にのみ適用されます.
例えば
3日間の場合は100101です.
4日間で1000、1010、1001
5日間で10000、10100、10010、10001、10101
結果iが持つことができる個数は,i−1の末尾に0,i−2の末尾に01を加える.だからs[i]=s[i-2]+s[i-1]の場合が成立する.
Reference
この問題について((DP)白駿2193号が親水), 我々は、より多くの情報をここで見つけました https://velog.io/@jwun95/DP-백준-2193번-이친수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol