[BOJ]1904 01タイル


📃 タイル

コード#コード#

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

for k in range(3,n+1):
    dp[k] = (dp[k-1]+ dp[k-2])%15746
print(dp[n])

に答える


  • DP問題は少なくともn=>5まで直接計算し,ルールを探す.

  • 出力が大きすぎるため、15746に分割された値が出力され、その過程で注意すべき部分が出力される.
  • 結果はスコアだけでなく、繰り返し文でもいつでも残りの演算を行うことで、メモリオーバーが発生しません.(n=10000の場合、int値を超えるため、メモリが大量に消費されます.)