[백준 11727] 2xn 타일링 2(DP)

문제

 

풀이

 

경우의수를 통해 규칙성을 발견해 

dp[i] = dp[i-1] + 2 * d[i-2]

 

이라는 점화식을 세웠다.

 

 

코드

n = int(input())
dp = [0] * 1001

# 초기값 지정
dp[0] = 1
dp[1] = 1


for i in range(2, n+1):
    dp[i] = dp[i-1] + 2 * dp[i-2]

print(dp[n]%10007)

 

*주의

dp = [0]*(N+1)로 dp배열을 만들 수 있지만, 이 경우 N=0인 경우에 dp[1]을 참조할 수 없게 된다 (런타임 에러 (IndexError) 발생)

주어진 입력이  1 ≤ n ≤ 1,000 이므로, 처음부터 크기가 1001으로 배열의 크기를 지정해서 런타임에러를 방지할 수 있다.

그게 아니라면, 런타임 에러를 방지하기 위해 아래와 같이 코드를 작성해야 한다

N = int(input())
if N == 0:
    result = 0
elif N == 1:
    result = 1
elif N == 2:
    result = 3
else:
    dp = [0] * (N + 1)
    dp[1] = 1
    dp[2] = 3

    for i in range(3, N + 1):
        dp[i] = dp[i - 1] + 2 * dp[i - 2]

    result = dp[N] % 10007

print(result)