[백준] 곱셈 JAVA

반응형

728x90

[백준] 곱셈 - SILVER I 1629번

---

접근

• 빠른 거듭제곱

---

풀이

곱셈이라는 제목의 문제로 설명을 대충 봤을 땐 이게 왜 실버 1의 문제인 건지 이해할 수 없는 내용의 문제이다. a, b, c 세 정수가 있고 a를 b번 곱한 결과에 c를 나눈 나머지를 출력하는 문제이다. 처음에 a와 b를 곱한 값에 c를 나눈 나머지를 출력하는 문제인 줄 알고 바로 제출했다 한 번 틀렸고 a의 b제곱을 구하는 문제인지 다시 인지한 후에 아무 생각 없이 Math.pow를 사용하여 제출했다 또 틀렸다. 문제에 주어진 값의 최대가 Integer.MAX_VALUE 이기 때문에 오버플로우가 났구나 하고 반복문으로 만들어 매번 c를 나눠 줬다가 또 틀렸다. 값의 최댓값이 21억인데 그걸 반복문으로 돌리려 했으니 통과할리가 없는데 말이다. 대충 봤을 때 너무 쉬워 보여 제대로 생각 안 하고 풀다가 몇 번이나 틀려버렸다.

 

그래서 이 문제에서는 빠른 거듭제곱 알고리즘을 사용해서 풀어야 한다. 이 방법은 주어진 수 b를 a의 거듭제곱 형태로 표현하는 것이다. 예를 들어 b가 13이라면 이진수로 1101 이 경우 2³ + 2² + 2⁰으로 표현할 수 있고 A² = A x A,  A⁴ = (A²)², A⁸ = (A⁴)²처럼 제곱을 이용해 지수를 줄여나갈 수 있다. 

	String[] input = br.readLine().split(" ");
        long a = Long.parseLong(input[0]);
        long b = Long.parseLong(input[1]);
        long c = Long.parseLong(input[2]);

입력 값들을 다 long 타입으로 파싱해 넣어줬다. 입력받는 시점 값 자체는 int형으로도 받을 순 있으나 계산이 이루어지면 int형 변수로는 바로 오버플로우가 나버리기 때문에 처음부터 long 타입으로 받아줬다.

	long result = 1;
        a %= c;

 결과를 담을 변수도 역시 long으로 선언해주고 주 연산이 곱하기로 이루어지기 때문에 초기값이 0이 아닌 1로 초기화해준다. a는 오버플로우 방지를 위해 모든 a가 들어간 연산마다 c를 나눈 나머지로 사용하게 된다. 

	while (b > 0) {
            if ((b % 2) == 1) {
                result = (result * a) % c;
            }

            b /= 2;
            a = (a * a) % c;
        }

b가 0보다 클 때 반복으로 b가 0이 되면 계산이 완료되었다고 보면 된다. 동작 원리는 b가 홀수 일 경우 직접적으로 곱하기 연산을 수행하게 되고 b가 짝수라면 a를 제곱하여 준다. 이게 무슨 말이냐면 A⁶ 처럼 제곱수가 짝수인 경우 (A³)² 와 같이 바꾸어 한 번에 A²을 나누거나 곱하여 계산할 수 있다. 그러나 A⁷처럼 제곱수가 홀수인 경우는 (A³)² x A처럼 앞의 계산을 한 뒤 한 번 더 남는 A를 곱해줘야 하기 때문에 while문 아래에서 홀수인 경우 뒤에 남는 A를 곱해주는 연산을 실행하는 것이고 짝수인 경우 제곱을 통해 지수를 한 번에 줄여나가는 방식으로 계산을 하는 것이다. 이 방식은 시간 복잡도가 O(logB)이기 때문에 큰 수의 거듭제곱을 효율적으로 계산할 수 있다. 

---

전체 코드

import java.io.*;

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

        String[] input = br.readLine().split(" ");
        long a = Long.parseLong(input[0]);
        long b = Long.parseLong(input[1]);
        long c = Long.parseLong(input[2]);

        long result = 1;
        a %= c;

        while (b > 0) {
            if ((b % 2) == 1) {
                result = (result * a) % c;
            }

            b /= 2;
            a = (a * a) % c;
        }


        System.out.println(result);
        br.close();
    }
}