📝 문제

처음에는 무턱대고 고등학생 때 배운 수학 지식으로 풀어보았다.
나머지를 제곱하고 c로 나눈 후 그 나머지를 제곱하여 다시 나누기를 반복...
하지만 시간초과가 났다. 당연한 결과였다. b의 최댓값이 2,147,483,647인데
2,147,483,647번 반복한다는 거 자체가 시간초과이다💢

그래서 다른 방법을 생각해보았고, 거듭제곱 연산의 시간복잡도를 줄이기 위한 방법 중 하나인 분할정복으로 풀어보기로 했다.

분할정복

분할정복 알고리즘은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 병합하여 답을 찾는 알고리즘 방식이다.

• 병합정렬 (시간복잡도: O(nlongn))
  1. (분할) 나누어진 배열의 길이가 1이 될 때까지 배열의 길이를 2로 나눈다.
  2. 조각난 두 집합의 배열을 병합하면서 정렬한다.
  
• 거듭제곱 (시간복잡도: O(log N))
  1. 일반적으로 n거듭제곱 연산은 자신을 n번 곱해야 함으로 O(N)의 복잡도를 가진다.
  2. 하지만 연산 방법을 조금만 바꾸어 보면 A^n = A^(n/2) * A^(n/2) 이다.
  3. 이렇게 지수를 반으로 나누어 가면서 재귀형식으로 알고리즘을 진행한다.

모듈러의 성질

우리가 모듈러 연산에서 알고 있으면 좋은 성질이 있다.

• (A + B) % C = (A%C + B%C) % C
• (A B) % C = (A%C B%C) % C

📌 코드

package Mathmetics;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1629 {

 static long mod(long a, long b, long c){
   // exponent == 1 : return a mod c
   if(b == 1){
     return a % c;
   }
   // recursion
   long result = mod(a, b/2, c);
   // 모듈러 성질
   // if exponent is odd : one more multiply itself
   if(b % 2 == 1){
     return (result * result % c) * a % c;
   }
   return result * result % c;
 }

 public static void main(String[] args) throws IOException {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(br.readLine());
   long a = Long.parseLong(st.nextToken());
   long b = Long.parseLong(st.nextToken());
   long c = Long.parseLong(st.nextToken());
   // 나머지를 제곱하고 c로 나눈 후 그 나머지를 제곱하여 다시 나누기를 반복 (시간초과)
   // 분할정복
   // 모듈로 성질 : (a * b) % c = ((a % c) * (b % c)) % c
   long answer = mod(a, b, c);
   System.out.println(answer);
 }
}