C# 백준 18291 비요뜨의 징검다리 건너기(분할 정복 알고리즘)

18291번: 비요뜨의 징검다리 건너기

IDEA

현재 위치에서 1~N까지의 범위 안에 자유롭게 이동이 가능하다. 브루트포스로 작성하는 것도 가능하겠지만 기상청 컴퓨터를 빌려써야 할 것 같다. N개의 징검다리가 있을 때, N이 1이라면 출발점과 도착점이 같은 것이기 때문에 경우의 수는 1이고 2 이상일 때부터 출발점과 도착점 사이의 징검다리들을 각각 밟을 것인지 건너 뛸 것인지 선택하는 것과 같다. N - 2 개의 징검다리 중 1개만 밟는 경우, 2개만 밟는 경우, 3개만 밟는 경우, ..., N - 3 개를 밟는 경우, N - 2개를 모두 밟는 경우를 더해주면 된다. 식으로 나타내면 이렇다.

 

f(n) = _n-2C₁ + _n-2C₂ + _n-2C₃ + ... + _n-2C_n-4 + _n-2C_n-3 + _n-2C_n-2 = 2 ^n-2

 

결국 2의 거듭제곱을 구하라는 말이다. 문제는 주어진 N의 범위가 너무 크다는 것인데 최대 무려 1,000,000,000까지 주어진다. 1,000,000,007로 나눈 값을 구하면 되기 때문에 넘어갈 때마다 나눠주면 되겠지만 이걸 하나하나 다 곱하고 있기에는 제한시간 1초가 너무 부족하다.

using System;
class Program
{
    static int T, N;
    static int div = 1000000007;
    static void Main()
    {
        T = int.Parse(Console.ReadLine());
        for(int i = 0; i < T; i++)
        {
            N = int.Parse(Console.ReadLine());
            int res = 1;
            for(int j = 2; j < N; j++)
            {
                res *= 2;
                res %= div;
            }	// 시간 복잡도 O(n)
            Console.WriteLine(res % div);
        }
    }
}

 

이럴 때 복잡한(여기서는 너무 반복적인) 문제를 작은 문제로 쪼개서 해결하고 합쳐주는 분할 정복 알고리즘을 적용하면 좋다. 분할 정복 알고리즘은 큰 문제를 작은 문제로 나누고 최소 단위로 나누어진 문제들을 해결한 다음 결과들을 조합해 원래 문제의 결과를 얻는 방법이다.

 

2ⁿ = 2^n/2 * 2^n/2 (n이 짝수), 2ⁿ = 2^(n-1)/2 * 2^(n-1)/2 * 2 (n이 홀수)

 

이 방법을 이용하면 O(log n) 의 시간 복잡도를 갖는다. 재귀를 활용하면 간단하게 표현 가능하지만 호출 시간에 약간 손해를 본다. 반복문을 쓰는 편이 더 좋지만, 재귀는 bottom-up 방식으로 보면 바로 이해가 되지만 반복문은 top-down 방식으로 표현되어서 다른 분들의 코드를 보면서 이해하는데 한참 걸렸다.

 

CODE

using System;
class Program
{
    static int T, N;
    static ulong div = 1000000007;
    static void Main()
    {
        T = int.Parse(Console.ReadLine());
        for(int i = 0; i < T; i++)
        {
            N = int.Parse(Console.ReadLine());
            Console.WriteLine(Power(2, N - 2) % div);
        }
    }
    static ulong Power(ulong a, int n)
    {
        ulong res = 1;		// 곱하는 과정에 overflow를 일으키기 때문에
        			// ulong을 썼다. (그냥 long으로 해도 될 것 같다.)
        while(n > 0)
        {
            if(n % 2 == 1)	// n이 홀수인 경우
            {
                res *= a;	// a를 결과에 곱해준다.
                res %= div;
                n--;		// n을 짝수로 만들어준다.
            }
            a *= a;		// a를 제곱한다.
            a %= div;
            n >>= 1;		// 비트를 오른쪽으로 한칸 밀어준다.
        }			// 2로 나누는 것과 같은 효과를 내지만
        			// 실제 연산을 실행하는 것이 아니기 때문에
                     	   	// 이게 좀 더 빠르다.
        return res;
    }
}