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

문제번호: 11726

문제명: 2xn 타일

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

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

 

요즘 계속해서 DP문제를 연습하고 있기 때문에 오늘도 DP문제를 풀어보았습니다.

11726번은 n개의 타일을 채울 수 있는 경우의 수가 1과 2가 존재합니다. 따라서 n을 받아오고 1과 2로 n을 만들 수 있는 경우의 수를 구하는 코드를 만들었습니다. 그런데 계속 틀리길래 이유를 찾아보니 n이 몇십만 되어도 모든 자료형을 초과하기 때문에 한계가 없는 BigInteger를 사용하였더니 통과하였습니다. 다음은 정답코드입니다.

public static void Main() // 경우의 수: 1개 채우거나 2개 채우거나
{
    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 = 3; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}