[Baekjoon, C++] 1629번 : 곱셈

백준 단계별 풀기에서 분할정복 네 번째 문제이다.

링크는 아래와 같다.

www.acmicpc.net/problem/1629

1629번: 곱셈

---

백준 1629번 문제, 입력, 출력

---

백준 1629번 입출력 예제 1

---

1. 시간복잡도를 생각해 보아야 하는 문제이다. 단순히 a^n 하면 시간 복잡도는 얼마인가? O(n)이다. 시간 복잡도가 무엇인가? 어떤 프로그램 또는 알고리즘이 수행하는데 소요되는 시간을 보여주는 것이라고 볼 수 있다. $$2^n > n^3 > n^2 > n*logn > n > logn > 1$$ 순이다. 

시간 복잡도

n에 따른 시간복잡도

여기서 분할정복 메커니즘을 활용한 알고리즘을 사용하면 O(log n)의 복잡도의 알고리즘으로 문제를 해결할 수 있다. 알고리즘 출처는 아래와 같다.

en.wikipedia.org/wiki/Exponentiation_by_squaring

Exponentiation by squaring - Wikipedia

이곳에서 설명하는 이진 지수 거듭 제곱은 예를 들어 $$ x^9 $$이 있다면, 9은 이진법으로 $$1001_2$$이고, $$x^8*x^1$$로 표현할 수 있다. x의 거듭제곱을 다음과 같이 2로 쪼개서(재귀) 해당 하는 숫자들만을 계산하는 방식을 2의 Exponentiation by squaring 방식이라고 한다. 

 

2. 데이터 타입을 어떻게 할 것인가, 지수계산을 처리하는데 있어서 도중에 데이터 타입이 수용할 수 있는 크기보다 넘어설 수 있다. 그래서 long long 타입을 써서, 범위를 수용할 수 있게끔 합니다. 

자료형 크기 표

자료형을 int로 사용하였을 때

---

#include<iostream>

using namespace std;
long long int a;
long long int b;
int c;

long long int APowerB(long long int a, long long int b) {
	if (b == 0) // 거듭제곱이 0일때는 무조건 1
		return 1;
	else if (b == 1)  // 거듭제곱이 1일때는 계속해서 a 반환
		return a;
	if (b % 2 > 0)   // 거듭제곱을 2로 나눈 나머지.
		return APowerB(a, b - 1) * a;
	long long int binarySquaring = APowerB(a, b / 2);
	binarySquaring %= c;

	return (binarySquaring * binarySquaring) % c;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> a >> b >> c;

	cout << APowerB(a, b) % c;
	

	return 0;
}

---

이상으로 1629번 문제를 마치겠다.