[Baekjoon/백준] 1629번: 곱셈(C/C++)

단계별로 풀어보기 20단계(분할 정복) 4번 문제

https://www.acmicpc.net/step/20

분할 정복 단계

---

백준 1629번: 곱셈

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

1629번: 곱셈

---

문제 설명

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

---

입력과 출력

입력: 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력: 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

---

접근 방법

이번 문제는 자연수 A, B, C를 입력받고, A^B / C의 나머지를 출력하는 문제다.

단순하게 생각하면 반복문을 통해서 A^B 연산을 하고, % 연산자로 C로 나눈 나머지를 구하면 되겠지만, 입력 조건에서 보이듯이 숫자가 최대 21억으로 매우 크고, 이를 제곱해야 하므로 일반적인 연산을 한다면 무조건 시간 초과가 발생할 것이다.

따라서 재귀를 통한 분할정복으로 제곱을 구해서 문제를 해결해야한다. 우선 A^B에서 B가 0일경우 A 값에 상관없이 무조건 1이 된다. 그리고 B가 1이라면, A가 된다. 이점을 이용해서 A^B를 계속 분해하면서 재귀를 해주면 된다.

A^B를 분해하는 것은 B가 짝수인지 홀수인지로 나뉜다. B가 짝수라면 B를 반으로 나눠서 재귀를 해주고, B가 홀수라면 A^B = A * A ^ (B-1)로 분해하면 된다. 이를 계속 반복하면서 나온 값을 C로 나눠주면 문제를 해결할 수 있다.

개인적으로 이런 수학 문제는 진짜 너무 어렵고 까다로워서 이 블로그 글을 참고해서 진행했다. 아마 다음 문제들도 다 수학 문제들이라서... 비슷하게 진행될 것 같다.

---

코드

#include <iostream>
using namespace std;

long long int pow(long long int A, long long int B, long long int C) {
	if (B == 0)	return 1;
	if (B == 1)	return A;

	if (B % 2 != 0)
		return A * pow(A, B - 1, C);

	long long int temp = pow(A, B / 2, C);
	temp %= C;
	return (temp * temp) % C;
}

int main(int argc, char *argv[]) {
	long long int A, B, C;
	cin >> A >> B >> C;

	cout << pow(A, B, C) % C << endl;

	return 0;
}

---

결과

백준 제출 결과