[Silver I][JAVA] 1436번:곱셈

문제 풀이

백준 1629번 곱셈은 실버 1 난이도의 수학 및 분할 정복 문제이다. 이 문제에서는 자연수 A, B, C가 주어진다. 이때 (A^B) % C를 구하면 된다.

이 문제는 간단한 거듭제곱처럼 보이지만 그렇게 간단하지만은 않다. 이 이유는 문제에서 0.5초 시간제한이 있다. 그래서 이 문제는 Math.pow를 사용해서 풀 수가 없다. 이제 그 이유를 설명해 보겠다.

예를 들어서 E ^ a를 구해보겠다. 기본 Math.pow의 코드는 다음과 비슷하다.

  static long pow(int x, int power) {
    if (power == 0)
      return 1;
    long result = 1 L;

    for (int k = 1; k <= power; k++) {
      result = result * x;
    }

    return result;
  }

따라서, 이 코드의 시간 복잡도는 O(power), 즉 우리의 경우에서는 O(a)가 된다. 이때, 이 함수를 써서 거듭제곱을 구하면 0.5의 시간제한을 초과하게 된다. 그래서 이 문제는 분할 정복의 'Exponentiation' 방법을 써서 풀어야 한다. 분할 정복의 방식을 쓰면 시간 복잡도는 O(log a)로 효율성이 훨씬 더 좋아지게 된다. 분할 정복을 이용한 방법은 다음과 같다.

즉 x^a = x^(a/2) * x^(a /2)이므로 이 수를 제곱해 주면 된다. 이 코드의 Pseudocode는 다음과 같다 (물론 여기는 짝수만 보는데 홀수인 경우도 처리해줘야 한다.

즉, 재귀를 이용한 방법으로 하면 시간 복잡도는 O(log a)가 된다. 트리 형태로 나타낼 경우 다음과 같이 나타낼 수 있다.

이 함수가 O(log a)인 경우는 log a 만큼의 레벨이 있다. 그리고 각 레벨에서 걸리는 시간은 O(1)이다. 따라서, O(log a) * O(1)을 하므로 O (log a)가 된다.

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

package baekjoon_java.SilverI;

import java.io.*;
import java.util.*;
/*
https://www.acmicpc.net/problem/1629
시간제한 0.5 , 메모리 14292KB, 시간 120ms
 */
public class 곱셈 {
    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());
        System.out.print(exponentiation(a, b, c));
    }

    public static long exponentiation(long a, long b, long c) {
        if (b == 0) return 1;
        if (b % 2 == 1) {
            return (a * exponentiation(a, b - 1, c)) % c;
        }
        long k = exponentiation(a, b / 2, c) % c;
        return (k * k) % c;
    }
}