[baekjoon] 백준 11726번(파이썬): 2×n 타일링

문제

11726번: 2×n 타일링

알고리즘

- 점화식을 구해보면 n = 1일 때, 1이고 n = 2일 때, 2이고 n = 3일 때, 3이고 n = 4일 때, 5이고 n = 5일 때, 8인 것을 확인할 수 있다. (dp[n] = dp[n - 1] + dp[n - 2])

- n이 3보다 작거나 같을 때 직사격형을 채우는 방법의 수가 n개 이므로 n을 출력한다.

- 그 외인 경우에는 점화식을 통해서 문제를 수행한다.

코드

import sys
sys.setrecursionlimit(10 ** 6)

# 점화식 : n = 1 일때 1, n = 2 일때 2, n = 3 일때 3, n = 4 일때 5, n = 5 일때, 8
n = int(sys.stdin.readline())
dp = [0] * (n + 1)

# n이 3보다 같거나 작을 때는 직사각형을 채우는 방법의 수가 n개이다.
if n <= 3:
    print(n)
# n보다 크다면 점화식을 통해 문제를 수행
else:
    dp[1] = 1 # n = 1 일때 1
    dp[2] = 2 # n = 2 일때 2

    # 반복문을 통해 점화식을 코드로 수행
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    # n일때 경우의 수에서 10007로 나눈 값을 출력
    print(dp[n] % 10007)

 

실패한 코드(시간 초과)

import sys
sys.setrecursionlimit(10 ** 6)
# 점화식 : n = 1 일때 1, n = 2 일때 2, n = 3 일때 3, n = 4 일때 5, n = 5 일때, 8
n = int(sys.stdin.readline())

def dp(v):
    if v == 1:
        return 1

    elif v == 2:
        return 2
        
    else:
        return dp(v - 1) + dp(v - 2)

print(dp(n))

n의 범위가 1보다 크거나 같고 1000보다 작거나 같기 때문에 위 코드를 통해 수행하게 되면 2^n의 시간 복잡도가 생기는 것으로 보인다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법