백준 1629

ALGORITHM
2025-09-03

곱셈

관련 개념

#분할정복 #모듈러 연산

문제

1629

📌 1 단계 : 문제 분석하기

  • 쉬워 보이지만 냅다 풀어보면 오버플로우와 시간 초과가 발생한다.
  • 이 문제는 오버플로우가 발생하지 않게 잘 분할 및 정복을 하는 문제이다.

📌 2 단계 : 손으로 풀어보기

  • 지수를 반으로 나눈다.
  • 지수가 1이 되면 결과를 반환한다.
  • 이때 모듈러 연산을 적절히 사용한다

📌 3 단계 : 슈도 코드 작성하기

  • 생략

📌 4 단계 : 코드 작성하기

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <numeric>
#include <algorithm>
#include <set>
 
using namespace std;
 
long long calculate(int A, int B, int C) {
 
	if (B == 1) return A % C;
 
	int mid = B / 2;
	// 오버플로우 방지
	long long value = calculate(A, mid, C) % C;
 
	// 짝수인 경우
	if (B % 2 == 0) {
		return (value * value) % C;
	} 
	else {
	// 모듈러 연산
		return (((value * value) % C) * (A % C)) % C;
	}
 
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	int A, B, C;
 
	cin >> A >> B >> C;
 
	cout << calculate(A, B, C);
 
}

📌 5 단계 : 배운점

  • 아래는 내가 처음에 제출했단 답안이다.
  • 여기에는 다음과 같은 문제가 있다
    1. 비효율성 - 같은 함수를 두번씩 호출함
    2. 오버플로우 - calculate를 곱했을 때 오버플로우가 발생한다면?
  • 위 코드는 이 문제들을 해결했다
  • 실버 문제지만, 모듈러 연산의 핵심, 분할정복 그리고 담을 수 있는 수의 범위에 대해서 생각해볼 수 있는 좋은 문제이다.
int calculate(int A, int B, int C) {
 
	int mid = B / 2;
 
	if (B == 1) return A % C;
	else return (calculate(A % C, mid, C) * calculate(A % C, B - mid, C)) % C;
 
}