728x90
📌 문제
문제)
곱셈 자연수 A를 B번 곱한 수를 알고 싶다.
단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력)
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다.
A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력)
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
시간 제한 : 0.5초
메모리 제한 : 128MB
📌 문제 분석❗️
❗️제곱을 분할
- A를 B번 곱한 수(제곱)은 다음과 같이 분할할 수 있다.
A⁹ = A⁴ * A⁴ * A¹
A⁴ = A² * A²
A² = A¹ * A¹
식을 보면 알다싶이 제곱 수는 계속 쪼갤 수 있다. 따라서 정복 분할을 통해 풀이가 가능하다.
❗️모듈러 연산(mod, %)
A를 B번 곱한 수를 C로 나눈 나머지를 정답으로 구해야 한다. 그러나 입력 숫자 A, B, C 모두 2,147,483,647 이하의 자연수이다. 이걸 마지막에 구한다고 한다면 Int 형이나 Long 형에 상관없이 표현할 수 있는 메모리가 초과되고 만다. 그래서 분할 정복을 할 때 모듈러 연산의 공식을 이용해서 나머지를 구해주어야 한다.
모듈러 합동 공식은 다음과 같은 식을 만족한다.
따라서 A⁴ % P = (A² % P * A² % P) % P 로 표현할 수 있다.
분할 정복 로직을 작성할 때 모듈러 합동 공식도 끼워 넣어주면 된다.
❗️B는 짝수? 홀수?
A⁹ = A⁴ * A⁴ * A¹ 처럼 맨 마지막에 A¹ 이 남는다. 따라서 홀수는 마지막에 A를 한 번 더 곱해주자.
📌 진행
❗️제곱 메서드 구현
- Parameter
base : 곱할 수(A)
exponent : base를 exponent 번 곱함(B)
P : 나눌 나머지(C) - 제곱 수 exponent를 반(half)으로 쪼갠다(범위 분할)
int half = exponent / 2;
long powerToValue = power(base, half, P);exponent를 반으로 쪼개 다시 재귀시켜 powerToValue에 입력 받음
- totalValue(재귀 결과 값 * 재귀 결과 값)를 구하고 거기에 모듈러 연산을 적용해준다.
long totalValue = (powerToValue * powerToValue) % P;예를 들어 A⁴ % P = (A² % P * A² % P) % P 이런 식으로 적용된다. 내부적으로 재귀 안에서도 모듈러 연산이 똑같이 수행된다.
- exponent가 홀수라면 base를 한 번 더 곱해주어 리턴한다.
if (exponent % 2 == 1) return (base * totalValue) % P;
else return totalValue;
📌 전체 코드
package level21_분할정복_.Q4_1629;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException{
int A = readInt();
int B = readInt();
int C = readInt();
long result = power(A,B,C);
System.out.println(result);
}
private static long power(int base, int exponent, int P) {
if (exponent == 0) return 1;
int half = exponent / 2;
long powerToValue = power(base, half, P);
long totalValue = (powerToValue * powerToValue) % P;
if (exponent % 2 == 1) return (base * totalValue) % P;
else return totalValue;
}
private static int readInt() throws IOException {
boolean isNegative = false;
int value = 0;
while (true) {
int input = System.in.read();
if (input == ' ' || input == '\n') {
return (isNegative) ? -1 * value :
value;
} else value = value * 10 + (input - 48);
}
}
}
댓글