백준 알고리즘 1629번: 곱셈

문제 정보

---

1629번: 곱셈

 

 

문제 파악

---

문제 조건

1 <= A, B, C <= 2,147,483,647 (자연수)

 

문제 내용

A를 B번 곱한 수를 C로 나눈 나머지를 출력

 

예시를 보면, A=10, B=11, C=12이다. 실제로는 이 수들을 나눈 나머지를 구해야 하지만, 예시를 들기 위해 나머지를 구하는 부분은 제외하고 설명해 보자면 위 그림과 같을 것이다.

이는 (a=b+c일 때) X^a = X^b * X^c 라는 수학적 공식을 사용하여 전개한 것이고, 이 식에서 지수 a가 짝수라면 지수가 a/2 인 두개의 수의 곱으로 표현되며 지수가 홀수라면 지수가 a/2 인 두개의 곱과 지수가 1인 수, 총 3개의 수의 곱으로 나타낼 수 있다.

 

우리는 이 문제를 풀기 위하여, 모듈러 합동 공식을 알아야 한다.

어쩌면 모두가 이미 알고 있을 공식일 수도 있는데, 이는 두 수(a, b)의 곱을 C로 나눈 나머지는 각각의 수를 C로 나눈 나머지를 다시 C로 나눈 나머지 라는 것이다.

 

우리가 이를 전개하게 되면 위와 같다.

우리가 해야할 일은 이미 알고있는 보라색(A^1 % C) 를 사용하여 노랑색 필드를 구하고,

이미 구했던 노랑색 필드와 같은 초록색 필드를 중복 계산하지 않고 값만 대입하여 불필요한 계산을 하지 않는 것이 중요하다.

물론 노랑색 필드를 구할 때에는, 위에 모듈러 합동 공식에 나온 것처럼 아래 자식 노드 두개를 곱한 후에 C로 나눈 나머지를 구하는 연산이 필요하다.

 

풀이

---

생각했던 내용

첫번째로 단순하게, dp가 떠오를 수 있다.

지수의 개수만큼의 dp 배열을 두고, 천천히 배열의 원소를 채워가며 불필요한 연산을 줄여갈 수 있다.

하지만 생각할 것은 지수의 개수의 최대값은 INT_MAX인 2^31-1 이다. 위 풀이를 진행하기 위해서는 dp 배열을 int의 최대값 크기만큼 동적 할당해야 하고, 이는 메모리 초과로 이어진다.

실제로 해봄

 

두번째는, dp 배열을 사용하지 않고 해당 값을 지역변수에 저장하여 재사용하는 것이다.

이 문제의 구조를 보면, 우리는 항상 (n/2 * n/2) or (n/2 * n/2 * 1) 로 쪼개어 간다.

long tmp = backtracking(n/2);

if(n%2 == 0) {
    return tmp * tmp % C;
} else {
    return (tmp * tmp % C) * A % C;
}

반을 나눠서 한쪽만 재귀호출을 통해 값을 구해나간다. 재귀 호출이 끝나면 tmp 에는 값이 저장되어 있을 것이다.

저장된 이 값을 두번 곱하여 새로운 현재 값을 구할 수 있다.

 

그렇게 되면 우리가 예시인 10, 11, 12를 입력했을 때,

backtracking(11) -> backtracking(5) -> backtracking(2) -> backtracking(1) = 10 % 12

총 네번만 호출하여 우리가 원하는 값을 구해낼 수 있다.

// input
10 11 12

// output
backtracking(11)
backtracking(5)
backtracking(2)
backtracking(1)
4

 

다만 주의해야 할 점은, tmp는 long 타입으로 지정해야 하는 것이다.

문제에서 주어진 각 변수들의 범위와, 자료형 int, long 의 범위는 다음과 같다.

우리가 계속 구해가는 것은 사실상 (~ % C) 즉 C로 나눈 나머지이기 때문에 C보다 무조건 작은 값이 tmp에 저장될 것이고,

그렇기 때문에 tmp는 int 형이여도 되지 않나? 라는 의문이 들 수도 있지만

 

B 가 짝수일 때, 위와 같은 식으로 부분을 축소할 수 있으며

만약 A=INT_MAX - 1, C=INT_MAX 의 값을 가지고 있다면,

 

B=2일 때, (INT_MAX-1 * INT_MAX-1) 에서 오버플로우가 발생하여 값이 정상적으로 구해지지 않는다.

if(n%2 == 0) {
    return tmp * tmp % C;

따라서 tmp를 long으로 하게 된다면 (tmp = INT_MAX-1) 이므로, tmp * tmp = (2^31-1 * 2^31-1) 이어서 long 범위 내에서는 안전하게 구해질 수 있는 것이다

 

 

풀이한 내용

두번째 풀이를 사용하여 풀이를 진행하였다.

 

코드

---

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

public class Main {
    static int A;
    static int B;
    static int 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(backtracking(B));
    }

    public static long backtracking(int n) {
        if(n==1) {
            return A % C;
        }

        long tmp = backtracking(n/2);

        if(n%2 == 0) {
            return tmp * tmp % C;
        } else {
            return (tmp * tmp % C) * A % C;
        }
    }
}

 

 

Source Code on GitHub

---