[백준] 1629 곱셈 (JAVA)

✉️문제

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

1629번: 곱셈

 

📝 접근

for문을 이용한 방법

가장 간단한 방법이 for문을 이용하여 a를 b번 곱해주는 것이다. 

for(int i = 0; i < b; i++) 
	a *= b;

 

하지만, 이 방법은 b가 50,000,000이 넘어가면 시간초과가 되어 버린다. (시간 제한 : 0.5).

따라서, O(N)보다 빠른 알고리즘을 고려할 필요가 있다.

 

분할 정복(Binary Search)

   분할 정복은 숫자의 1/2를 반복해서 구하는 것이다. 10^8을 분할 정복으로 구해보자.

짝수 분할 정복

먼저 왼쪽 그림에서 10^8이 10^4 두 개로 분할되는 것을 확인할 수 있다. 여기서 중요한 것은 일단 10^4의 값을 구하면 자기 자신을 한 번 더 곱함으로써 10^8의 값을 구할 수 있기 때문에 왼쪽으로 뻗어나가는 가지의 값만 구하면 이를 가볍게 해결 할 수 있다. 이 분할 정복을 이용하면 시간 복잡도가 O(log N)으로 줄어든다. 

 -> 10^4, 10^2, 10^1 값만 알면 10^8을 구할 수 있다.

 

그렇다면 홀 수의 경우는 어떻게 분할 정복을 해야 할까? 10^5를 분할 정복해보자.

홀수의 경우 밑을 한 번 더 곱해주면 된다.

홀 수 분할 정복

이를 코드로 표현해보자.

static long pow(long base, long exponent) {

    // 밑, 지수 = 1
    if(exponent == 1 || base == 1) 
    	return base;
    
    // 분할
    long tmp = pow(base, exponent / 2);
    
    // 홀 수
    if(exponent % 2 == 1)
    	return tmp * tmp * base;
        
    // 짝 수
    return tmp * tmp;
}

 

모듈러 연산

문제를 다시 한 번 확인해보자. 입력 값의 범위가 int의 MAX값 까지 주어질 수 있기 때문에 c로 나눈 나머지를 계산하도록 되어 있다. 이를 위해 모듈러 연산이 필요하다. 공식은 다음과 같다.

모듈러 합동 공식

이를 코드로 표현해보면 다음과 같다.

    static long pow(long base, long exponent) {
        if(base == 1 || exponent == 1)
            return base % c;

        long tmp = pow(base, exponent / 2);

        if(exponent % 2 == 1)
            return (tmp * tmp % c) * base % c;

        return tmp * tmp % c;
    }

 

🗝 문제풀이

import java.util.Scanner;

public class B1629 {

    static int a, b, c;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();

        System.out.println(pow(a, b));
    }

    static long pow(long base, long exponent) {
        if(base == 1 || exponent == 1)
            return base % c;

        long tmp = pow(base, exponent / 2);

        if(exponent % 2 == 1)
            return (tmp * tmp % c) * base % c;

        return tmp * tmp % c;
    }
}

 

 

다음 블로그를 참고하여 작성하였습니다.

https://st-lab.tistory.com/237