[백준] 1629: 곱셈 (재귀, 모듈러성질) - JAVA

class4

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

 

 

 

 

# 문제

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

 

# 예제

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

10 11 12

 

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

4

 

# 필요개념

문제를 봤을 때 간단한데 ? 생각했다가 제한시간이 0.5초인 것을 보고 쉽진 않겠다는 생각을 했다. 단순히 Math.pow() 함수를 사용하면 시간초과가 발생한다. pow를 사용하면 최악의 경우 n = 21억이 되므로 O(n) 시간복잡도를 갖는 방법은 사용할 수 없다.

 

추가로 주어지는 숫자의 크기가 매우 크므로, 정답을 넣어두는 변수는 long 타입으로 지정하였다.

 

이 문제의 경우 재귀를 이용해 구한다. 만약 3^16 을 구해야 하는 경우, 3을 16번 곱하는 것보다는

3^8 * 3^8

(3^4 * 3^4) * ( 3^4 * 3^4)

((3^2 * 3^2) * ( 3^2 * 3^2)) * (( 3^2 * 3^2) * ( 3^2 * 3^2))

 

이런식으로 구하면 시간을 훨씬 줄일 수 있다!

private static long myPow(int a, int b, int c) {
        if (b == 1) return a;

        long sol = myPow(a, b / 2, c);
        if (b % 2 == 1) {
            return sol * sol * a;
        }
        return sol * sol;
    }

 

재귀를 이용해 코드를 작성하면 이렇게 쓸 수 있다.

 

문제에 c로 나눈 나머지를 구하라는 조건이 한 가지 더 있다. 이 조건을 잘 이용하려면 모듈러 합동 공식을 알고있어야 한다. 

 

이 공식을 적용하면 우리는 아래 식을 풀어야한다.

• (sol * sol * a) % c
  • = ((sol * sol % c) * a) % c
    • (sol * sol) 이 long의 범위를 벗어나지 않기 때문에 위 식에서 a로, 기존 a를 b로 치환하였다) 

 

그럼 아래와 같이 코드를 작성할 수 있다.

 

# Code

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        long ans = myPow(A, B, C);
        System.out.println(ans);

    }

    private static long myPow(int a, int b, int c) {
        if (b == 1) return (a % c);

        long sol = myPow(a, b / 2, c);
        if (b % 2 == 1) {
            return sol * sol % c * a % c;
        }
        return sol * sol % c;
    }
}

 

# 결과