백준 1629 - 곱셈(나머지 분배법칙, 지수법칙, JAVA)

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

1629번: 곱셈

간단 설명 : 자연수 A를 B번 곱한 수를 C로 나눈 나머지 구하기

 

시간 제한은 0.5초인데 입력 값인 A, B, C의 범위가 1부터 2,147,483,647 이니까

시간복잡도를 잘 생각해서 코드를 짜야했다.

 

1. 나머지 연산 분배법칙

(A * B)%Q = (A%Q) * (B%Q)

A와 B를 곱해서 나머지 연산을 나눈 값과

A의 나머지, B의 나머지를 곱한 값이 같다는 뜻이다

 

이유를 간단히 설명해보면

A = aQ + R1 ( a = A를 Q로 나눴을 때 몫, R1 = A를 Q로 나눴을 때 값)

B = bQ + R2 라고 할 때

 

(A * B)%Q = (A%Q) * (B%Q) 이 식에 A와 B를 각각 대입해보면,

 

(aQ + R1) * (bQ + R2) % Q

 = (aQ + R1)%Q * (bQ + R2) % Q 이고

 

분배법칙으로 곱하면

(abQ제곱 + bQR1 + aQR2 + R1R2) % Q

= ((aQ + R1) % Q) * ((bQ + R2) % Q) 이다.

 

여기서 Q로 나눈 나머지를 구하므로 Q로 나눌 수 있는 수는 다 지운다.

그러면 R1R2 = R1R2 로 같다는 것을 확인할 수 있다.

 

# 그럼 모듈러 연산이 왜 필요할까?

A의 B제곱 마지막에 나머지를 구하려고 하면 값이 A의 값이 매우 클 때, 계산을 하는 중간에 값의 범위를 초과해서 에러가 나게된다.

그러므로 중간에 값의 나머지를 구하면서 수의 크기를 줄여도 나머지 분배법칙에 의해 결과값은 같다!

 

2. 시간초과

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(token.nextToken());
        int b = Integer.parseInt(token.nextToken());
        int c = Integer.parseInt(token.nextToken());
        int R = a % c;

        for(int i=0; i<b; i++){
            result *= R;
            result %= c;
        }
        System.out.print(result);
    }

 

그래서 나머지를 구하고 값을 계속해서 곱하면서 나머지를 구하는 방식으로 접근했는데,

값의 범위를 초과하지는 않았지만 시간초과가 났다.

아마 b의 값이 2,147,483,647 까지 될 수 있어서 반복문을 그만큼 돌려야되니까 시간초과가 난 것 같다.

 

3. 지수법칙

    public long square(long r, long s, long q){
        if(s == 1){
            return r;
        }

        long next = (r*r) %q;
        if(s%2 == 0){
            return square(next, s/2, q);
        }else{
            return square(next, s/2, q) * square(r, 1, q) % q;
        }
    }

 

지수법칙을 설명해보면 다음과 같다

이 법칙을 이용하면 지수값을 계속 /2 해서 1까지 줄일 수 있다!

 

r : 곱할 값(밑), s : 제곱할 수(지수), q : 나누는 수

일단 q 빼고 재귀가 작동하는 흐름을 설명해보자면

r = 2, s = 10 일때

f(밑, 지수)

f(2, 10)

↓

f(4, 5)

↓

f(16, 2) * f(4, 1)

↓

f(256, 1) * f(4, 1)

이런식으로 지수법칙에 의해 지수 값을 반으로 계속 줄일 수 있고

마지막으로 지수가 1이 되면 값을 반환하고 끝낸다.

 

여기서 q를 고려하는 이유는

long next = (r*r)

return square(next, s/2, q) * square(r, 1, q)

처럼 곱할 때마다 long 값의 범위를 넘을 수 있기 때문에 각각 q로 나눈 나머지를 구하도록 했다

 

# 마무리

나머지 분배법칙은 이전에 본 적이 있어서 쉽게 했는데

지수법칙은 금방 떠올렸지만 코드로 어떻게 풀어야할지 모르겠어서 오래걸렸다

실버 문제는 풀긴 풀더라도 2시간씩 걸리는데 언제 골드문제를 풀까나

끝!