[백준알고리즘/11727번/파이썬] 2xn 타일링 2

 

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

11727번: 2×n 타일링 2

 

문제: 2xn 직사각형을 1x2, 2x1, 2x2 타일로 채우는 방법의 수를 구하는 문제

 

풀이 방법: DP

 

풀이 코드:

n = int(input())
dp = [0] * (n+1)

dp[1] = 1

if n > 1:
    for i in range(2,n+1):
        if i % 2:
            dp[i] = dp[i-1] * 2 - 1
        else:
            dp[i] = dp[i-1]*2 + 1

print(dp[n] % 10007)

 

 

풀이 설명: 

 

문제를 보고 n 값에 따른 규칙성을 찾아보고자 하였습니다.

 

 

 

 

 

다음과 같이 2x1 , 2x2 , 2x3 짜리 직사각형이 있다고 할 때, 경우의 수는 다음과 같습니다.

 

2x1일 경우,  2x1 직사각형 1개로만 채울 수 있습니다.

 

2x2인 경우, 2x1 짜리 2개로 구성하는 방법, 1x2짜리 2개로 구성하는 방법, 2x2 짜리 1개로 구성하는 방법으로 총 3가지가 있습니다.

 

2x3 짜리는 어떨까요?

 

2x1 짜리 3개로 구성하는 방법, 2x1짜리 1 개와 2x2짜리 1개  또는 2x1짜리 1개와 2x1짜리 2개 로 구성하는 방법으로 총 5가지가 있습니다.

 

2x4짜리는 위와 같은 방법으로 총 11개의 방법이 있는데요.

 

n = 1 일 때부터 4일 때 까지 경우의 수를 보니 다음과 같은 규칙성을 발견할 수 있었습니다.

 

n이 홀수일 경우, n-1번째 경우의 수 * 2 - 1

n이 짝수일 경우, n-1번째 경우의 수 * 2 + 1 이라는 규칙을 구할 수 있었습니다.

 

따라서, 다음과 같이 코드를 구성해 n번째 경우의 수를 구하였습니다.

 

if n > 1:
    for i in range(2,n+1):
        if i % 2:
            dp[i] = dp[i-1] * 2 - 1
        else:
            dp[i] = dp[i-1]*2 + 1

 

또한, 10007로 나눈 나머지를 출력하라 하였으므로 다음 코드를 통해 구한 경우의 수를 10007로 나눈 나머지를 출력하도록 하였습니다.

print(dp[n] % 10007)