[백준] 1629번 : 곱셈

문제

정수 A, B, C가 주어졌을 때

A를 B번 곱한 값을 C로 나누었을 때 몫을 구하라

 

접근 방식

문제 자체는 엄청 간단한 문제지만 시간제한과 메모리 제한이 걸려있기 때문에

반복문이나 재귀로 하나하나 다 곱하고 나누면 통과할 수 없는 문제다.

(값의 표현 범위를 벗어나기도 한다)

 

반복문으로도 풀 수 있고 재귀로도 풀 수 있는 문제지만

재귀를 공부할 겸 재귀로 풀어보았다.

 

우선 반복문으로 풀면 메모리 초과가 발생할 일은 없지만

재귀로 풀 때는 조심해야 할 부분이 있는데

재귀 호출을 B만큼 반복하면 호출 스택에 그만큼 쌓여

B의 값이 큰 경우에는 메모리가 초과되기 때문에

재귀 호출을 최대한 줄이는 방식으로 풀어야 한다.

 

(x ^ n) * (x ^ n) = x^2n

 

위와 같은 법칙을 생각해서 풀면 되는데

만약 10의 10승을 구한다면 10의 5승까지만 구해도

10의 5승을 제곱하면 10의 10승이기 때문에

계산 횟수를 줄일 수 있다.

 

(9 ^ 7) % 7

9 2
18 4
36 1
9 2
18 4
36 1
9 2
18 4

 

또한 값을 계속 곱해주다 보면 int나 long 타입으로

표현할 수 있는 값의 범위를 벗어나게 되는데

위의 계산 순서에서 알 수 있듯이

그때 그때 나눠준 후에 제곱을 해도

몫은 항상 같기 때문에

값의 범위를 벗어나는 것을 방지할 수 있다.

 

풀이

public class Main {

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

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

		long a = Long.parseLong(st.nextToken());
		long b = Long.parseLong(st.nextToken());
		long c = Long.parseLong(st.nextToken());

		System.out.println(calculate(a, b, c));
	}

	private static long calculate(long a, long b, long c) {
		if (b == 1) return a % c;
		long result = calculate(a, b/2, c);
		result = (result * result) % c;
		if (b % 2 == 0) {
			return result;
		}
		return (a * result) % c;
	}
}