[13주_6일차] 백준-11726 2xN 타일링(Python)

문제

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

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

입력

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

 

출력

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

 

 

<코드>

def num_ways_to_tile(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = (dp[i-1] + dp[i-2]) % 10007
    
    return dp[n]

n = int(input())

print(num_ways_to_tile(n))

 

<풀이과정>

• DP 배열 정의:
  • dp[i]를 2×i 크기의 직사각형을 채우는 방법의 수라고 정의
• 점화식:
  • 2×n 크기의 직사각형을 채우는 방법의 두 가지 경우:
    1. 마지막에 2×1 타일 하나를 세로로 놓는 경우: 남은 공간은 2×(n-1) 크기. 즉, 이 경우는 dp[n-1]에 해당
    2. 마지막에 1×2 타일 두 개를 가로로 놓는 경우: 남은 공간은 2×(n-2) 크기. 즉, 이 경우는 dp[n-2]에 해당
  • 점화식: dp[n]=dp[n−1]+dp[n−2]
• 초기값 설정:
  • dp[1] = 1: 2×1 크기의 직사각형을 채우는 방법은 1가지
  • dp[2] = 2: 2×2 크기의 직사각형을 채우는 방법은 2가지 (2×1 타일 두 개 또는 1×2 타일 두 개)
• 결과 계산:
  • 최종 결과를 10,007로 나눈 나머지를 출력해야 하므로, 각 DP 값을 계산할 때마다 10,007로 나눈 나머지 구하기