사용한 알고리즘

• DP

알고리즘 설명

• 이 문제는 2xn 타일링 DP 문제로 이미 유명하다
• DP 점화식 유도과정은 아래와 같다
• 길이가 2xn인 타일링을 만드는 방법은 2x(n-1) + 2x1 or 2x(n-2) + 2x(1x2) or 2x(n-2) + 2x2 3가지 경우이다
• 결국 n>=2에 대해서 dp[n]=dp[n-1] + 2 * dp[n-2]
• 여기서 dp[0]의 경우의 수는 아무것도 없는 경우를 세어 1개로 정해야한다
• n이 250 이하의 정수로 c++의 64bit에 저장하기에 무리가 있다.
• 파이썬에서는 c++보다 높은 수의 연산을 지원하므로 이를 이용하였다.

풀이

// baekjoon 1793
dp=[0]*251
dp[0]=1
dp[1]=1
dp[2]=3
for i in range(3,251):
    dp[i] = dp[i-1]+2*dp[i-2]

while True:
    try:
        n = int(input())
        print(dp[n])
    except:
        break