[백준] 11726 - 2×n 타일링

1. 문제

11726번: 2×n 타일링

2. 개요

기초 dp문제.

1 * 2 크기의 타일로 2 * n 크기의 타일을 채울 때의 경우의 수를 구하는 문제.

3. 코드 및 추가내용

블록 형태로 생각하지 말고 숫자로 치환해서 생각하면 더 간단해진다.

타일을 세워 1칸을 채우는 경우를 1, 눕힌 타일 2개로 2칸을 채우는 경우를 2로 생각하면 된다.

즉 어떤 수를 1과 2의 합으로 만드는 모든 경우의 수를 구하는 문제이다.

3.1 Python

import sys

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

dp = [1, 1] + [0 for i in range(2, n+1)]

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

print(dp[n])

3.2 C#

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

			if (n < 2) { Console.WriteLine(1); }

			else
			{
				int[] dp = new int[n + 1];
				dp[0] = 1;
				dp[1] = 1;

				for (int i = 2; i < n+1; i++)
				{
					dp[i] = (dp[i - 2] + dp[i - 1]) % 10007;
				}
				Console.WriteLine(dp[^1]);
			}
		}
	}
}