[분할 정복] 수퍼바이러스_소프티어

문제: 수퍼바이러스_소프티어

source: https://softeer.ai/practice/info.do?idx=1&eid=391

---

풀이

처음 바이러스가 K라면,
1초 후: K x P x ... x P = K x P^10
2초 후: (K x P^10) x P x .. x P = K x P^20
..
N초 후: K x P^(Nx10)

단순히

ull answer = K;
answer *= pow((ull)(P), N * 10);

이렇게 답을 도출할 수 있지만 중간 중간 과정에서 MOD(=1000000007)로 모듈러 연산을 해줄 수 없다. 이럴 경우 unsigned long long 형식으로 담을 수 없다.

그렇고 O(N)의 시간복잡도로 진행하면서 모듈러 연산을 해줄 순 없다. 시간초과가 발생한다. 아래는 시간초과가 발생한 풀이 방법이다.

#include <iostream>
using namespace std;

typedef long long ll;
const int MOD = 1000000007;

int K, P;
ll N;

int getP_10(int P) {
	ll ret = 1;
	for (int i = 0; i < 10; i++) {
		ret = (ret * P) % MOD;
	}

	return ret;
}

int CalcOneSec(int k, int P_10) {

	return (int)(((ll)k * P_10) % MOD);
}

int main() {
	cin >> K >> P >> N;

	int P_10 = getP_10(P);

	for (ll i = 0; i < N; i++) {
		K = CalcOneSec(K, P_10);
	}

	cout << K << endl;
}

따라서 O(logN) 시간 복잡도로 해결하는 풀이가 있어야 한다. 아래는 분할 정복 방식으로 해결한 풀이이다.

#include <iostream>
using namespace std;

typedef unsigned long long ull;
const int MOD = 1000000007;

int K, P;
ull N;

int getP_10(int P) {
	ull ret = 1;
	for (int i = 0; i < 10; i++) {
		ret = (ret * P) % MOD;
	}

	return ret;
}

ull DivideAndConquer(ull n, int P_10) {
	// 종료 조건
	if (n == 1)
		return P_10;

	
	ull ret = 1;
	if (n % 2 == 0) {
		ull halfRet = DivideAndConquer(n / 2, P_10);
		ret = (ret * halfRet) % MOD;
		ret = (ret * halfRet) % MOD;
	}
	else {
		ull halfRet = DivideAndConquer(n / 2, P_10);
		ret = (ret * halfRet) % MOD;
		ret = (ret * halfRet) % MOD;
		ret = ret * P_10 % MOD;
	}

	return ret;
}

int main() {
	cin >> K >> P >> N;
	
	// 1초 후: K * P * ... * P = K * P^10
	// 2초 후: (K*P^10) * P * ... * P = K*P^20
	// ..
	// N초 후: K*P^(N*10)

	// 답은 간단히 아래와 같이 산출할 수 있지만, 중간 중간 과정에서 MOD(= 1000000007)로 모듈러 연산을 해줄 수 없다.
	// 이럴 경우 unsigned long long 형식으로 담을 수 없을 수 있다.
	//ull answer = K;
	//answer *= pow((ull)(P), N * 10);



	int P_10 = getP_10(P);

	ull answer = K;
	ull gob = DivideAndConquer(N, P_10);
	answer = (answer * gob) % MOD;

	cout << answer << endl;
}

참고로 아래와 같이 분할 정복하면 O(N)과 다를 게 없다.

	if (n % 2 == 0) {
		ret = (ret * DivideAndConquer(n / 2, P_10) ) % MOD;
		ret = (ret * DivideAndConquer(n / 2, P_10)) % MOD;
	}
	else {
		ret = (ret * DivideAndConquer(n / 2, P_10)) % MOD;
		ret = (ret * DivideAndConquer(n / 2, P_10)) % MOD;
		ret = ret * DivideAndConquer(1, P_10) % MOD;
	}