💡문제 분석 요약

-- 문제 --

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력 : 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력 : 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

💡알고리즘 설계

계산 과정에서 int 범위를 벗어날 수 있음 → long 사용
B가 최대일 때, 시간 초과 → 제곱을 분할하는 방식 : 모듈러연산, 지수 법칙

💡코드

package backjoon;

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

public class BackJoon1629 {
    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.println(pow(a,b,c));
    }

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

💡시간복잡도

O(log N)

💡틀린 이유

💡틀린 부분 수정 or 다른 풀이

💡느낀점 or 기억 할 정보

int 범위 = –2,147,483,648 ~ 2,147,483,647
모듈러 연산 : 8 mod 4 일때 0123 기준으로 시계 방향으로 4번 돈다.

(사진 출처: https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic,
https://st-lab.tistory.com/237)

모듈러 연산 특징
1. 합 분배 : (A+B) mod C = (A mod C + B mod C) mod C
2. 뺄셈 분배 : (A-B) mod C = (A mod C - B mod C) mod C
3. 곱 분배 : (A*B) mod C = ((A mod C) * (B mod C)) mod C

[ 백준 ] 1629 - 곱셈 (with.Java)