백준 1629 - 곱셈(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1629

1629번: 곱셈

분할정복을 이용한 거듭제곱을 활용해 푸는 문제였습니다.

 

A를 B번 제곱을 그냥하게 되면 long long 범위도 벗어나기 때문에 다른 방법이 필요합니다.

또한 B의 범위가 21억이기에, 시간 초과가 생길 수도 있습니다.

이때 사용하는 방법이 분할 정복을 활용한 거듭제곱입니다.

 

먼저 제곱을 하는 코드를 만들어 보겠습니다.

    int ans = 1;
    for(int i = 1; i <= N; i++){
        ans *= X;
    }
    
    //////////////////////////////////////// 혹은 //////////////////////////////////
    
    ans = pow(X,N);

가장 간단한 코드지만, N번을 그대로 실행하기에 O(N) 의 시간을 가집니다.

 

이를 빠르게 만들 수 있는 방법을 규칙을 통해 확인해보겠습니다.

이는 거듭제곱의 성질을 통해 분할 정복을 이용하여 확인할 수 있습니다.

 

따라서 코드를 확인해보겠습니다.

int multiple(int x, int y){
    if(y == 1) return x;
    else{
        int multi = pow(x , y/2);
        if(y % 2 == 0) return multi * multi;
        else return x * multi *multi;
    }
}

이번에는 O(logN)으로 시간이 많이 줄은 것은 확인할 수 있습니다.

 

이번 문제에서는 하나를 더 확인해야합니다.

데이터의 값이 크면 변수의 범위보다 커질 것이 확실함으로 계속 나머지를 구해주는 것이 중요합니다.

 

따라서 재귀를 사용해서 분할 정복을 계속 하되, 함수 값을 return 할때마다 나머지 값으로 return 해주는 것입니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>

using namespace std;

int A, B, C;

long long int multiple(int x, int y, int z) {
	if (y == 1) return x;
	else {
		long long int multi = multiple(x, y / 2, z);
		if (y % 2 == 0) {
			return (multi * multi) % z;
		}
		else {
			return ((multi * multi) % z * x) % z;
		}
	}
}

void solve() {
	cout << multiple(A % C, B, C);
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> A >> B >> C;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요