[백준 BOJ 1629번] 곱셈

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

1629번: 곱셈

 

1. 문제

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

---

2. 입력

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

 

10 11 12

---

3. 출력

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

 

4

---

4. 풀이

일단 분할 정복인 부분부터가 큰 힌트였다. 먼저, 이렇게 큰 수들의 곱셉 및 나눗셈들의 과정이 나오면 분할 정복을 의심해봐야 한다. 이 문제의 경우 가장 어려웠던 부분은 %계산의 시기를 정하는 부분이었고 중요한 부분은 자료형의 선택의 부분이었다. 21억~~을 고려하면서 자료형을 long으로 두어도 되는지를 생각해봐야 했다. 크게 어려운 부분은 없고 구하고자 하는 값의 지수부분을 /2씩 해가면서 1일 경우 return을 하며 다시 conquer해가는 부분만 잘 해결하면 쉽게 풀 수 있었다.

---

5. 소스코드

import java.io.*;
import java.util.*;

public class Main {
    static long C;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        C = Long.parseLong(st.nextToken());
        System.out.println(result(A, B));
    }

    static long result(long a, long b) {
        if (b == 1)
            return a % C;

        long temp = result(a, b / 2);
        if (b % 2 == 0) {
            return (temp*temp) % C; //temp*temp는 long형을 넘어가지 않기에 %C를 해주지 않아도 되지만, 아래dml return문의 경우엔 temp*temp*a가 long형을 넘어가므로 각각 %C를 해주어야 한다.
        }

        return (temp%C * temp%C) * a%C;
    }
}

---

6. 배운 것

큰 수들을 다룰 땐 분할 정복을 생각해보자.

 

자료형의 선택을 잘 고려하고 overflow가 일어나지 않게 항상 조심하며 %계산을 해주자.