[백준] 11727 - 2xn 타일링 2

1. 문제

11727번: 2×n 타일링 2

2. 개요

2 x n 타일을 1 x 2, 2 x 1, 2 x 2 타일로 채우는 모든 경우의 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

1 x 2, 2 x 1 타일로만 채우는 문제가 있었는데, 이는 자연수 n을 1과 2의 합으로 나타내는 경우의 수와 같았다.

이때는 2 x n-1 타일을 채운 경우에 2 x 1 타일을 붙이는 경우와 2 x n-2 타일을 채운 경우에 1 x 2타일을 붙이는 경우를 합친 경우가 그 답이 된다.

이번에는 2 x 2타일이 추가되었고 이는 2 x n-2 타일을 채운 경우 1 x 2타일을 채워넣는 경우 뿐만 아니라 2 x 2 타일을 채워넣는 방법으로도 2 x n 타일을 완성할 수 있다.

따라서 식이 dp[n] = dp[n-1] + dp[n-2] * 2 가 된다.

답은 10007로 나눈 나머지를 출력해야 하기 때문에 항상 10007로 나눈 나머지를 dp테이블에 넣어주고 이를 출력해주면 된다.

3-2. Python

import sys

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

dp = [0 for i in range(1001)]

dp[1], dp[2] = 1, 3

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

print(dp[n])

3-3. C#

namespace boj_11727
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            int[] dp = new int[1001];

            dp[1] = 1;
            dp[2] = 3;

            for (int i = 3; i < n + 1; i++)
                dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;

            Console.WriteLine(dp[n]);
        }
    }
}