[알고리즘][Python] 백준(BOJ) 11726 2xn 타일링_파이썬

DP

11726 2xn 타일링    https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

 

 

 

문제 풀기 전 공부할 것 : DP

 

 

 

 

 

 

 

풀이 

2xN의 타일링의 경우

1. 2x(N-1) 타일링에 2x1 타일을 붙이는 경우
2. 2x(N-2) 타일링에 1x2 타일 2개를 붙이는 경우

1과 2의 경우의 합이므로 dp(N) = dp(N-1) + dp(N-2)가 점화식이 된다.

 

n = int(input())

dp = [0] * (n+1)

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

res = dp[n] % 10007
print(res)

 

 

 

 

 

 

 

시도 1 ==> 런타임 에러

n = 1인 경우 dp[2] = 2로 설정하여 에러가 발생한다.

이와 같은 문제를 해결할 때 IndexError: list assignment index out of range 의 에러를 조심해야 한다.

 

n = int(input())

dp = [0] * (n+1)

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

res = dp[n] % 10007
print(res)

 

 

 

시도 2 ==> 시간 초과

dp를 저장하는 부분이 없어 시간 초과가 발생한다.

 

import sys
sys.setrecursionlimit(10**6)

def solve(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    return solve(n-1) + solve(n-2)

n = int(input())
print(solve(n)%10007)

 

 

 

복습

런타임 에러시 문제의 원인 알기