[백준] 곱셈(1629)

GGANI·2021년 6월 5일
0

algorithm

목록 보기
7/20

문제

[백준] 곱셈(1629)

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

입력

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

출력

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

해설

처음엔 Math.pow()를 사용해 풀이가 가능하다고 생각했다. 만약 가능했다면 분할 정복 알고리즘으로 분류된 문제 중에서도 상단에 위치했을 텐데(보통은 상단에 위치한 문제들이 쉬운 편이라고 생각한다.) 중간에 위치한 이유가 있었겠지..😂

그리고 입력으로 주어지는 값은 모두 2,147,483,647 이하의 자연수이기 때문에 a, b 모두가 2,147,483,647라면 값의 범위가 어마어마해지기 때문에 다른 풀이 방법이 필요하다고 생각했다.

결국 다른 분의 풀이를 참고해 풀 수 있었고 많은 공부가 되었다.

참고 블로그(👍강추👍)
https://st-lab.tistory.com/237

블로그에도 나와 있듯이 지수 법칙모듈러 성질에 대한 이해가 필요한 문제였다.

먼저 이 문제가 분할 정복 알고리즘으로 분류된 이유도 지수 법칙을 기반으로 하기 때문이라 생각한다.

아래는 혹시나 다음에 비슷한 유형의 문제를 풀이할 때의 헷갈릴 수 있는 부분에 대해 자세하게 적어둔 것이다. (여기서 A는 밑이다.)

(B * A) % C = (B % C) * (A % C) % C
	    = ((temp * temp % C) * (A % C)) % C
            = ((temp * temp % C) % C) * (A % C % C) % C
            = ((temp * temp % C) % C) * (A % C)) % C
            = ((temp * temp % C) * A) % C

그리고 구현한 코드가 어떻게 수행되는지 궁금하면 예시를 하나 정해서 직접 손으로 써보는 것도 좋은 방법이라 생각한다.

예를 들어 입력이 2 4 3으로 주어졌을 때 출력은 1이다.

이걸 구현한 코드에 넣어서 생각해보면

1. pow(2, 4) 호출
2. pow(2, 2) 호출
3. pow(2, 1) 호출
4. 지수(exponent)가 1이므로 if(exponent == 1) return A % C 즉, 2를 리턴
5. pow(2, 1) 호출 결과로 temp에 2를 저장(식으로 표현하면 A % C)
6. temp가 짝수이므로 temp * temp % C = 1을 리턴
(식으로 표현하면 ((A % C) * (A % C)) % C = A^2 % C)
7. pow(2, 2) 호출 결과로 temp에 1을 저장
8. (6)번과 동일한 결과로 1을 리턴
9. pow(2, 4) 호출 결과로 temp에 1을 저장
10. output으로 1을 출력

풀이

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

public class Main {
	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(), " ");

		long a = Integer.parseInt(st.nextToken());
		long b = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());

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

	public static long pow(long a, long exponent) {
		if (exponent == 1)
			return a % c;

		long temp = pow(a, exponent / 2);

		if (exponent % 2 == 1)
			return (temp * temp % c) * a % c;

		return temp * temp % c;
	}
}
profile
능력있는 개발자를 꿈꾸는 작은아이

0개의 댓글