/ BOJ

BOJ_1629_곱셈_JAVA

문제 : 곱셈

링크 : BOJ_1629_곱셈

접근 방식

A의 B제곱 C로 나눈 나머지를 구해야 한다. 그냥 계산하면 되잖아? 라고 생각할 수도 있는 문제이지만, A,B,C의 범위가 모두 2147483647 이하의 자연수, 즉 제곱까지 생각하면 일단 값부터 계산할 수 있는 범위를 한참 벗어나게 된다. 또한 매 계산마다 C로 나머지연산을 해준다고 해도 시간제한이 0.5초이기 때문에 시행 횟수에서도 시간초과가 날 수밖에 없다. 따라서 이 문제는 단순계산으로 풀 수 있는 문제가 아니다.

분할정복을 이용해서 거듭제곱을 구할 수 있다.

만약 2^10 제곱이 있다고 하자. 이를 구하는 방식은 어떻게 구할 수 있을까. 먼저 2를 10번 곱해서 구하는 방식이 있을 수 있다. 또 다른 방법은 뭐가 있을 까?

2^5 * 2^5 와 같은 식으로도 구할 수 있다. 그렇다면 2^5는 어떻게 구할 수 있을까

2^2 * 2^2 * 2 와 같은 식으로 구할 수 있다.

2^2는 또 2^1 * 2^1로 나누어질 수 있다.

이렇게 큰 문제가 작은 문제로 쪼개어 계산되는 것, 분할정복이다.

거듭제곱을 구하는 일반항은 다음과 같의 정의된다

C^n = C^(n/2) * C^(n/2) : n이 홀수일 때 C^n = C^(n/2) * C^(n/2) * C : n이 짝수일 때

위 식을 이용하여 재귀함수를 통해 구현한다면, 기존의 연산속도가 획기적으로 줄어든다. C^n을 단순연산할 때 시간복잡도를 O(N)이라면, 분할반복을 통해 거듭제곱을 구하는 시간복잡도는 O(logN)이다.

풀이 방법

  1. 각 A,B,C변수에 값을 읽어들여 저장한다.

  2. 재귀를 통해 거듭제곱을 구해준다. 기저조건은 b가 0이 되면 1을 리턴하는 것으로 잡고, 위에서 설명한 일반항 대로 로직을 구성한다. 매 계산이 이루어질 때마다 %c를 해주어 값의 범위가 C 이내에서만 돌게 한다.

  3. 재귀를 모두 마친 후 결과값을 출력한다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1629_곱셈 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine()," ");

		long A = Long.parseLong(st.nextToken());

		long B = Long.parseLong(st.nextToken());

		long C = Long.parseLong(st.nextToken());

		long answer = fpow(A,B,C);

		System.out.println(answer);
	}

	public static long fpow(long a, long b, long c) {

		if(b == 0) {
			return 1;
		}

		long X = fpow(a,b/2, c);

		if(b%2==0) {
			return X*X%c;
		}else {
			return (X*X%c)*a%c;
		}

	}

}