[백준] 1629번: 곱셈 - JAVA

🔗 문제 링크

BOJ 1629번: 곱셈

📝 풀이 과정

주어진 숫자를 제곱해야 하는데 단순하게 반복문으로 제곱수를 구하게 되면 시간복잡도는 B의 크기만큼 소요되게 되고 B의 최대 크기는 $2^{31}-1$로 시간 제한을 초과하게 된다. 따라서 정해진 제곱을 분할하는 방식을 사용해 시간을 줄여야 한다.

 

 

$$
A^{10} = A^{5 + 5} = A^5 \times A^5
$$

먼저 제곱은 위의 식처럼 분할이 가능하다. 따라서 제곱을 순차적으로 하나씩 곱하면서 구하지 않고, $A^5$를 구한 뒤 그 수를 제곱하면 $A^{10}$을 쉽게 구할 수 있는 것이다. 만약 제곱수가 11(홀수)이라면 $A^5$(절반)를 제곱한 뒤 그 수에 $A$를 곱하면 되기 때문에 빠르게 답을 구할 수 있게 된다!

 

 

static long pow(int a, int b, int mod) {
  if (b == 0)
    return 1;

  long n = pow(a, b / 2, mod);
  if (b % 2 == 0)
    return n * n % mod;
  else
    return (n * n % mod) * a % mod;
}

이를 활용해 $a^b$의 값을 계산하는 pow(int a, int b)를 만들 수 있다. 주어진 값이 매우 크기때문에(int의 최대값) 계산하는 값을 long으로 선언해 주었고, 식이 계산될 때마다 mod를 통해 나눠주어야한다. b = 0이라는 것은 $A^0 = 1$이기 때문에 해당하는 수를 반환해주었다.

 

 

⏱ 시간 복잡도

주어진 B의 값을 계속 절반으로 줄여가며 계산하기 때문에 이는 $\log n$ 에 해당한다.
따라서, 시간복잡도는 $O(\log N) = O(\log (2^{31}-1)) < 31$ 이 된다

 

 

💻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt(), B = sc.nextInt(), C = sc.nextInt();

        System.out.println(pow(A, B, C));
    }

    static long pow(int a, int b, int mod) {
        if (b == 0)
            return 1;

        long n = pow(a, b / 2, mod);
        if (b % 2 == 0)
            return n * n % mod;
        else
            return (n * n % mod) * a % mod;
    }
}

📊 제출 결과