[백준] 곱셈 - Java

문제 출처

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

문제

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

입력

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

출력

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

예제 입력 1 복사

10 11 12

예제 출력 1 복사

4

풀이 방법

• 간단하게 분할 정복 알고리즘을 이용하여 풀이하였다.
• A의 B제곱은 아래와 같이, 해당 그림과 같이 나누어 풀이할 수 있다!
  • 그냥 A을 B번 곱하게 되면, 최대 정수형 범위 최대 수 만큼의 곱을 수행하므로 비효율적임(시간초과 가능성)

• 재귀를 통해, 다음과 같이 함수를 나눈 다음 재귀 끝에서 다시 합을 더해주면 끝.
  • 이 때, 홀수 인 경우가 있는데 홀수인 경우에는 *A를 한번 수행한다( /2 하면 홀수는 1이 잘려나감 )

풀이 코드

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

public class Main {
    static int A, B, C;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());


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

    public static long powMod(int A, int B, int C){
        if(B == 0){
            return 1;
        }

        long half = powMod(A, B / 2, C);
        long result = (half * half) % C;

        if(B % 2 != 0){
            result = (result * A) % C;
        }
        
        return result;
    }
}

결과

회고

• 분할정복 이해하기가 좀 어려운데, 관련 문서를 찾아봐야겠다.