자연수 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;
}
}