[백준/11726] 2×n 타일링 - 파이썬(Python)

문제

2 × n 크기의 직사각형을 1 × 2, 2 × 1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2 × 5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

11726번: 2×n 타일링

 

문제풀이

2×n 크기의 직사각형을 1 × 2, 2 × 1 타일로 채우는 방법의 수를 구하는 프로그램을 작성해야 한다.

우선, 길이가 n이라는 직사각형이 있을 때 피보나치와 유사한 형태의 식이 세워지는 것을 알 수 있다.

 

n = 1 : 1, n = 2 : 2, n = 3 : 3, n = 4 : 5, n = 5 : 8

n의 방법의 수는 n-1 + n-2라고 볼 수 있다. 즉, dp[n] = dp[n-1] + dp[n+1]이다. 

방법 1. 전체 값을 구한 후 출력

 

import sys
input = sys.stdin.readline

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

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

• 1 <= n <= 1000 범위이므로 1001만큼 만든다.
• dp[1]과 dp[2]의 초깃값을 설정하고 이후 1000번까지 결과를 저장한다.
• dp[n] % 10007 결과를 출력한다.

 

방법 2. n번까지의 값을 구한 후 출력

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * (n+1)
if n < 3:
    print(n % 10007)
else:
    dp[1], dp[2] = 1, 2

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

    print(dp[n] % 10007)

• n이 3 미만일 경우, print(n % 10007)로 결과를 화면에 바로 출력한다.
• n이 3 이상인 경우, dp[1]과 dp[2]를 초깃값을 설정한다.
• n번까지 결과를 저장한다.
• dp[n] % 10007 결과를 출력한다.

 

방법 3. dfs를 이용

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(num):
    if arr[num] > 0:
        return arr[num]
    if num == 1:
        return 1
    elif num == 2:
        return 2
    else:
        arr[num] = dfs(num-1) + dfs(num-2)
        return arr[num]
     
n = int(input())
arr = [0] * (n+1)
print(dfs(n) % 10007)

 

• 재귀 함수의 경우, 깊이 제한이 있어(기본 설정 1000회) Recursion Error가 날 수 있다. (나처럼 ^^;)
• sys.setrecursionlimit(10**6)를 추가하도록 한다.
• 참고로 PyPy를 사용할 경우 sys.setrecursionlimit()으로 임의로 재귀의 최대 깊이를 설정할 수 없다. 

 

시간 차이가 좀 날 줄 알았는데, 역시 비슷하다 !