[C#] 백준 11727번 문제풀이

문제번호: 11727

문제명: 2xn 타일링 2

문제링크: https://www.acmicpc.net/problem/11727

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다.

 

오늘도 DP문제를 풀어보았습니다. 이번 문제는 어제와 유사한 문제였기에 좀 더 수월하게 풀 수 있었습니다.

어제 풀었던 11726번 2xn 타일링 문제는 경우의 수가 1개로 채우거나 2개로 채우거나 2개였는데 이번 문제는 그 2개로 채우는 경우의 수가 2개로 늘었습니다.

그래서 이번엔 조금 헤매다가 질문 게시판을 둘러보다가 힌트를 얻었습니다.

말 그대로 2로 채우는 경우의 수가 2개니까 dp [-2] * 2가 되는 것입니다. 이번 문제를 풀어보며 아직 점화식을 찾는 것이 많이 미숙하다는 것을 느꼈습니다. 더 노력해야겠습니다 ㅠㅠ

다음은 정답코드입니다.

 

public static void Main()
{
    int N = int.Parse(Console.ReadLine());

    Console.WriteLine(Calculate(N) % 10007);

    BigInteger Calculate(int n)
    {
        if (n <= 1) return 1;


        BigInteger[] dp = new BigInteger[n + 1];
        dp[0] = dp[1] = 1;
        dp[2] = dp[0] + dp[1];

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

        return dp[n];
    }
}