CP予想問題04
タイルタイプ
1)2 xnタイル1 x 2、2 x 1タイルを用いて充填する方法の数
https://www.acmicpc.net/problem/1172
#11726 2 x n타일링 1x2,2x1타일로 채우는 방법의 수
#n=1일때 방법의수 1개, n=2일때 2개, n=3일때 3, 4일때 5,5일 때 8
# 점화식 dp[n]= dp[n-2]+dp[n-1] (n개에서 타일을 채울수있는 방법의 수)
# n-2는 누워있는 타일2개 / n-1은 세워진 타일 하나를 뜻함
n= int(input())
dp=[0,1,2]+([0]*(1001-3))
for i in range(3,1001):
dp[i]=dp[i-2]+dp[i-1]
print(dp[n]%10007)
2)2個のnタイル1 x 2、2個のx 1、2個のx 2タイル充填方法の数
https://www.acmicpc.net/problem/11727
#11727 2 x n타일링 1x2,2x1,2x2타일로 채우는 방법의 수
#n=1일때 방법의수 1개, n=2일때 3개, n=3일때 5...
# 점화식 dp[n]= 2*dp[n-2]+dp[n-1] (n개에서 타일을 채울수있는 방법의 수)
# n-2는 누워있는 타일2개, 종류가 2가지니까 *2 / n-1은 세워진 타일 하나를 뜻함
n= int(input())
dp=[0,1,3]+([0]*(1001-3))
for i in range(3,1001):
dp[i]=2*dp[i-2]+dp[i-1]
print(dp[n]%10007)
Reference
この問題について(CP予想問題04), 我々は、より多くの情報をここで見つけました https://velog.io/@phj9908/CP-예상문제-04テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol