도입

• 백준 13172번 문제를 풀기 위해 배운 개념을 정리한다.

개요

• 분할 정복(Divide and Conquer)이란 커다란 문제를 조금씩 나눠서 쉽게 풀 수 있는 문제 단위로 나누어 해결하고 이를 합쳐서 큰 문제를 해결하는 개념이다.
• 거듭제곱에 있어서, $C^n$은 일반적으로는 C를 n번 곱하므로 Big-O 표기법에 따라 $O(n)$이지만, 분할 정복을 통해 $O(logn)$으로 시간을 줄일 수 있다.

설명

• 분할 정복을 이용한 거듭제곱은 $C^n$이 아래와 같이 표기할 수 있다는 것에서 비롯된다.
  
• 위 수식에서 위는 $n$이 짝수일 경우, 아래는 $n$이 홀수일 경우 지수가 모두 자연수가 되도록하기 위해 맞춘 식이다.
• 이처럼 $C^n$은 어떤 수를 두 번 곱한 것으로 표현할 수 있다.
• 즉, $C^{n/2}$나 $C^{(n- 1)/2}$을 구하면 C를 $n/2$ 번 더 곱하지 않고 한번의 곱셉 계산으로 $C^n$을 구할 수 있고, 이는 $C^{n/2}$도 마찬가지이므로 $log_2n$번의 계산만 필요하다는 걸 알 수 있다.

적용 예시

• 백준 13172번 Σ 풀이 예시

#include <iostream>
#define MOD 1000000007
#define ll long long
using namespace std;

int M;
ll N, S, answer = 0;

ll power(ll n, ll m)
{
	ll result = 1;
	while (m)
	{
		if (m & 1)
			result = result * n % MOD;
		m = m / 2;
		n = n * n % MOD;
	}

	return result;
}

void input()
{
	cin >> M;

	while (M--)
	{
		cin >> N >> S;

		answer += (S * power(N, MOD - 2)) % MOD;
	}
}

int main()
{
	input();
	cout << answer % MOD;
	return 0;
}

참고

• [Algorithm] 분할정복을 이용한 거듭제곱
• [알고리즘] Divide and Conquer (분할정복)
• 모듈러 산술(Modular Arithmetic)
• 분할 정복 알고리즘 | 나무위키