분할-정복 알고리즘(Divide-Conquer)

[개념]

data-make.tistory.com/232

[Algorithm] 분할 정복(Divide & Conquer)

 

 

 

 

 

[관련 문제 - 1]

www.acmicpc.net/problem/16943

16943번: 숫자 재배치

#include <iostream>
using namespace std;

int a, b, c;

//a^7 = (a^3)^2 * a
int pow(int n, int k) {
	if (k == 0) return 1;
	if (k == 1) return n;

	long long tmp = pow(n, k / 2);

	if (k % 2) {
		return (((tmp * tmp) % c) * a) % c;
	}
	else {
		return (tmp * tmp) % c;
	}
}

int main() {
	cin >> a >> b >> c;

	cout << pow(a % c, b) << endl;
}

 

 

 

 

 

[관련 문제 - 2]

https://www.acmicpc.net/problem/18291

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

#include <iostream>
//#include <cmath>
using namespace std;
typedef long long ll;
const ll M = 1e9 + 7;

//n의 범위가 10억이 넘기 때문에 분할 정복 사용 
int pow(int a, int b) {
	if (b == 0) return 1; //중요!

	ll mul = pow(2, b / 2);

	//짝수면
	if (b % 2 == 0) {
		return (mul * mul) % M;
	}
	//홀수면
	else {
		return (a * (mul * mul % M)) % M;
	}
}

int main() {
	int tc;
	cin >> tc;

	while (tc--) {
		int n;
		cin >> n;

		long long ans = 0;
		if (n == 1) {
			cout << 1 << endl;
			continue;
		}
		else {
			cout << pow(2, n - 2) << endl;
		}
	}
}