[백준 1629] 곱셈 (C/C++)

 

Problem

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

Comment

이 문제의 핵심은 두 가지입니다.

• 재귀 함수를 이용한 거듭 제곱 계산으로 시간 복잡도 성능 향상
• 모듈러 연산을 이용해 큰 수가 나오지 않도록 조정

 

거듭 제곱 계산을 재귀 함수로 짜는 방법은 아래 포스트에 게시되어 있으니 참고하시기 바랍니다.

https://laurent.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-2-%EC%9E%AC%EA%B7%80-recursion#3.1.%20%EC%9D%91%EC%9A%A9:%20[%EB%B0%B1%EC%A4%80%201629]%20%EA%B3%B1%EC%85%88

 

위 포스팅에서 제시하고 있는 거듭 제곱 계산 재귀 함수는 숫자의 크기를 신경쓰지 않은 코드입니다. 어차피 문제에서 물어보는 것은 나머지의 값을 물어보는 것이기 때문에 모듈러 연산을 통해 큰 수를 다 저장하지 않으면서 계산해야 합니다.

 

하지만 기존의 코드에서는 모듈러 연산을 사용해도 획기적으로 숫자를 줄일 수 없습니다. 기존의 코드를 한 번 보겠습니다.

double power(double x, int n) {
	if (n == 0) {
		return 1;
	} else if ((n % 2) == 0) {
		return power(x * x, n / 2);
	} else {
		return x * power(x * x, (n - 1) / 2));
	}
}

 

이 함수에서 가장 큰 문제점은 인수로 주는 x 값이 어떠한 필터링도 거치지 않고 값 그 자체로 들어가기 때문입니다. 작은 수라면 그렇게 큰 문제가 되지 않겠지만, 큰 수에서는 치명적으로 작용합니다. 따라서 이 문제에서는 인수로 넘기기 전 값을 따로 빼 모듈러 연산을 진행 한 후 계산합니다.

 

$$(A + B) \bmod M = ((A \bmod M) + (B \bmod M)) \bmod M$$

 

Code

#include <stdio.h>

long long power(long long a, long long b, long long c) {
  if (b == 1)
    return a % c;
  long long k = power(a, b / 2, c) % c;
  if (b % 2 == 0) {
    return k * k % c;
  } else {
    return k * k % c * a % c;
  }
}

int main() {
  long long a, b, c;
  long long res;
  scanf("%lld %lld %lld", &a, &b, &c);

  res = power(a, b, c);
  printf("%lld\n", res);
}

 

Result