[python backjun]11726|2 xNタイル

884 ワード
python algorithm テキストリンク

Try to solve 💭
nが1,2,3,4の前にタイルを描いて手を偽ってみたいときには,1,2,3,5の順に現れる.縦の長さを固定したタイルに横方向のみ延伸する構造なのでDP問題だと思います.2 x 3のタイルでは、「2 x 2+2 x 1」の大きさが「2+1=3」の値にちょうど合っていたが、4で例外が発生した.重なる部分があるので、アプローチを直接変えました.
n=4の場合、タイル構造は「2 x 2+2 x 2」、「2 x 3+2 x 1」とすることができる
n=5の場合、タイル構造は「2 x 4+2 x 1」、「2 x 3+2 x 2」とすることができる.
(「2 x 2+2 x 2+2 x 2+2 x 1」と同様の構造は、より大きなタイル構造において繰り返し添加されるため、除外される.)
->重複する部分を固定し、状況の数を求めればよい.
Solution 💡
最後のタイル.
1)2 x 1の構成を有する場合、
前に求められる数は2 x(n-1)のタイル型数値である.
2)2 x 2の構成を有する場合、
前に求められる数は2 x(n-2)のタイル型数値である.
すなわち、演算式はcase[n] = case[n-1] + case[n-2]と表すことができる.
Code Review 🔎
n = int(input())

case = [ 0, 1, 2 ]
mod = 10007

for i in range(3, n+1):
  result = case[i-1] + case[i-2]
  case.append(result % mod)
print(case[n])
[伯俊]10845-Q(Python)
Box Model