[백준 JAVA] 16953번: A -> B

https://www.acmicpc.net/problem/16953

 

백준 1629번 곱셈은 단순 구현처럼 보이지만 시간복잡도와 자료형을 동시에 고려해야 하는 전형적인 분할정복 문제다.
A를 B번 곱한 뒤 C로 나눈 나머지를 구하는 문제인데, B의 범위가 매우 크기 때문에 단순 반복문으로는 절대 해결할 수 없다.

처음 접근하면 A를 B번 곱하는 방식이 떠오르지만, 이 방법은 시간복잡도가 O(B)라서 B가 10억 수준이면 바로 시간초과가 난다.
그래서 이 문제의 핵심은 “지수를 줄이는 것”이다.

지수는 다음과 같이 나눌 수 있다.
B가 짝수라면 A^B는 A^(B/2)를 두 번 곱한 것과 같고,
B가 홀수라면 거기에 A를 한 번 더 곱하면 된다.

이걸 이용하면 계산 횟수를 절반씩 줄일 수 있다.
예를 들어 B가 13이라면 13 → 6 → 3 → 1처럼 계속 줄어들기 때문에 전체 연산 횟수는 log B 수준으로 떨어진다.

 

여기서 중요한 포인트는 두 가지다.

 

첫 번째는 곱셈을 할 때마다 반드시 mod 연산을 해줘야 한다는 점이다.
(a * b) % C는 (a % C * b % C) % C와 같기 때문에, 중간 과정에서도 계속 나머지를 취해주지 않으면 값이 커져서 오버플로우가 발생한다.

 

두 번째는 자료형이다.
곱셈 과정에서 값이 커지기 때문에 int가 아니라 long을 사용해야 안전하다.

재귀로도 구현할 수 있지만, 반복문으로 구현하면 스택을 쓰지 않아서 더 안정적이고 실전에서 많이 사용된다.
핵심 아이디어는 지수를 이진수로 보면서 필요한 경우에만 결과에 곱하는 방식이다.

아래는 반복문으로 구현한 코드다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        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());

        long result = 1;
        A %= C;

        while (B > 0) {
            if ((B & 1) == 1) {
                result = (result * A) % C;
            }

            A = (A * A) % C;
            B >>= 1;
        }

        System.out.println(result);
    }
}

 

반복문 방식뿐 아니라 재귀로도 많이 풀리는 문제다.
둘 다 본질은 같고, 단지 구현 방식만 다르다.

핵심은 “지수를 반으로 줄이면서 계산한다”는 점이다.
A를 B번 곱하는 대신, B를 계속 반으로 나누면서 계산 횟수를 줄인다.

재귀 방식은 이 아이디어를 그대로 코드로 옮긴 형태다.
기본 구조는 다음과 같다.

 

private static long pow(long a, long b) {
    if (b == 1) return a % C;

    long half = pow(a, b / 2);

    if (b % 2 == 0) {
        return (half * half) % C;
    } else {
        return (half * half % C) * a % C;
    }
}