백준 11726 2xn 타일링 파이썬 풀이

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

문제이해

입력받은 n만큼 세로 2 가로 n길이의 직사각형에  1x2 혹은 2x1 타일로 채우는 방법의 수를 구하면 된다. n의 입력값이 1000이기에 O(n^2)로 풀어도 되겠다는 생각은 들었다.

 

접근법

완전탐색을 사용하려 보니 재귀함수를 사용해야할거 같다는 생각으로 이어졌다. 하지만 파이썬에서는 기본적으로 재귀함수의 깊이 제한이 걸려있기 때문에 dp를 사용해야한다. 그래서 dp방법으로 풀이를 해보고자 했다.

 

코드

import sys

n = int(sys.stdin.readline().strip())

memo = {1:1, 2:2}

def  countBlock(n:int) -> int :
    
    for i in range(3, n + 1) :
        if i not in memo :
            memo[i] = memo[i - 1] + memo[i - 2]
    return memo[n]
print(countBlock(n)%10007)