백준 C# - 11726 +) 풀이

DP를 이용해서 풀어야한다.

DP알아보러 가기

C# - 다이나믹 프로그래밍(DP)

---

풀이

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제이다. 

그림에서 보면 끝에 부분이 2x1인 경우와 2x2인 2가지 경우로 나누어진다는 것을 확인할 수 있다.

01 2x1

2x1로 고정되어 있는 경우 경우의 수는 그 자리를 제외한 (n-1)!과 같다. 하지만 우리는 그 값을 dp[i-1]에 저장해놓았으므로 dp[i]에 그 값을 더해준다.

02 2x2

2x2로 고정되어 있는 경우 경우의 수는 그 자리를 제외한 (n-2)!과 같다. 하지만 우리는 그 값을 dp[i-2]에 저장해놓았으므로 dp[i]에 그 값을 더해준다.

03 점화식

dp[i] = dp[i-1] + dp[i-2]

 

---

02 n이 0과 1일때는 미리 지정

dp[0] = 1;
dp[1] = 2;

---

03 dp배열 채우기

문제에서  2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다고 했으므로 나눈 나머지를 저장한다.

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

---

코드 전문

using System;
namespace baek2
{
    class Program
    {
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            int[] dp = new int[n + 1];

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