[BaekJoon/백준] 1629번 분할정복

 

제곱을 구하는 문제인데, 처음에 일반적인 포문으로 구현했다가 시간초과가 났다.

그도 당연한것이, 제곱수의 최댓값은 약 21억인데 1억당 1초라고 계산해도 21초라는 시간이 걸리기 때문이다.

 

이 문제는 분할정복 개념을 이용해서 풀어야한다.

 

이렇게, 전체를 계속 반으로 쪼개서 반만 구한 뒤, 각 구한 값에 제곱만 해주면 본래 구하려던 값을 구할 수 있게 된다.

자세한 설명은 잘 기술되어 있는 블로그가 두 군데 있어서 링크를 참조!!

ga0n.tistory.com/entry/백준-1629번-곱셈

velog.io/@funhan/1629번-곱셈

 

#include <stdio.h>

long long A, B, C;

long long divide_conquer(long long a, long long b, long long c) {
    
    if(b == 1) return a % c;
    
    long long temp = divide_conquer(a, b/2, c);
    
    long long result = (temp * temp) % c;
    
    if(b % 2) result = (result * a) % c;
    
    return result;
}

int main() {
    
    long long result = 1;
    scanf("%lld %lld %lld", &A, &B, &C);
    
    result = divide_conquer(A, B, C);
    
    printf("%lld", result);
    
}

b == 1일때, return a % c 하는 이유는 아래 예외를 참고하면 된다.

www.acmicpc.net/board/view/49751