백준 5569, 11726 - 출근 경로, 2xn 타일링 [dp]

"""
백준 5569
"""
w, h = map(int, input().split())

dp = [[[[0 for __ in range(2)] for _ in range(2)] for j in range(w)] for i in range(h)]
for i in range(1,w): dp[0][i][1][0] = 1
for i in range(1,h): dp[i][0][1][1] = 1
# 0 0 회전 불가능 가로로
# 1 1 회전 가능 세로로
for i in range(1, h):
    for j in range(1,w):
        dp[i][j][0][0] = dp[i][j-1][1][1]
        dp[i][j][0][1] = dp[i-1][j][1][0]
        dp[i][j][1][0] = dp[i][j-1][0][0] + dp[i][j-1][1][0]
        dp[i][j][1][1] = dp[i-1][j][0][1] + dp[i-1][j][1][1]

print((sum(dp[-1][-1][0]) + sum(dp[-1][-1][1])) % 100000)

현재 블록에 가로라인으로 들어와서 회전이 불가능한 경우 = 회전이 가능한 세로로부터
현재 블록에 가로라인으로 들어와서 회전이 가능한 경우 = 회전 불가능한 가로 + 회전 가능한 가로
(회전 가능한 가로는 원래 가능했고 불가능했던 가로는 다음 칸에서 가능해지기 때문)

 

dp = [_ for _ in range(int(input())+1)]
for i in range(3,len(dp)):dp[i] = dp[i-2] + dp[i-1]
print(dp[-1] % 10007)

2*n 타일링

n-1에서는 1짜리 타일만 놓아서 n으로 올 수 있고, n-2에서는 2짜리 타일만 놓아서 n으로 올 수 있다 (1 짜리 2개 놓는 것은 위의 경우에 포함이므로 제외)

결론 : 피보나치 수열