[알고리즘] 백준 1629번 - 곱셈

문제 소개

백준 1629번 - 곱셈

문제가 매우 짧고 간단해서 엥? 싶었는데 자세히 뜯어보니 뭔가,, 뭔가 꼬롬했다.

꼬롬 1스택
매우 짧은 시간 제한

꼬롬 2스택
코린이에게는 그저 가혹하고 괴랄한 정답률

꼬롬 3스택
음,, 네

우선 결론부터 말하자면 자력으로 해결하지 못했다.

인터넷과 백준의 질문게시판을 참고하여 해결하였는데 생각보다 유명한 문제라고 한다.

우선 위와 같은 거듭제곱의 나머지를 구하는 형식의 문제는 모듈러 연산을 활용하여야 한다.

모듈러 연산의 특징을 이용해 거듭제곱의 나머지를 구하는 간단한 예시를 들어보자면,,

모듈러 연산의 특징

여기서 3번 특징을 사용하면,

이런 식으로 모듈러 합동을 이용해 나머지를 쉽고 빠르게 구할 수 있다.

위 풀이 과정과 같이, 우리는 지수가 1인 상태(위 그림에서는 생략)에서부터 나머지를 구해가면서 합동 연산과 곱셈 연산을 통해 나머지를 구하고 있다. 이러한 구조는 그림으로 나타내보았을 때,

이렇게 트리 형태를 가지는 구조로 바라볼 수 있다.

이제 각설하고 바로 코드로 넘어가보겠다.

#include <bits/stdc++.h>
using namespace std;

long long a, b, c, answer;

long long func(long long a, long long b, long long c) {
  if (b == 0) return 1;
  if (b == 1) return a % c;

    if (b % 2 == 0) {
    return (func(a, b / 2, c) % c) * (func(a, b / 2, c) % c) % c;
  } else {
    return (func(a, b / 2, c) % c) * (func(a, b / 2 + 1, c)) % c;
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> a >> b >> c;
  answer = func(a, b, c);
  cout << answer;

  return 0;
}

일단 21억이 넘는 수를 감당할 수 있는 자료형은 long long이므로 모든 변수를 long long으로 처리해주었다.

그리고 func라는 함수를 만들어 재귀적으로 모듈러 연산을 수행할 수 있도록 해주었는데 지수를 계속해서 2로 나누어주는 부분에서 짝수와 홀수의 처리가 다른 점에 신경을 써주었다.

짝수인 경우는 그냥 두 나머지를 곱하면 되지만 홀수인 경우는 지수법칙에 의해 b / 2 + 1을 인자로 넣어주었다. 위 tree 구조에서 5가 2와 3으로 나누어지는 case를 생각하면 될 듯하다.

역시 정답률 27% ㅋㅋ,,

분명 시간복잡도를 Olog(n)으로 잘 만들었다고 생각했는데 어디가 문제인지 정말 알 수 없었다.

아마 이 부분을 해결하는 것이 문제의 kick이라고 생각하고 열심히 삽질에 삽질을 해봤지만 아쉽게 해결하지 못하고 인터넷을 뒤졌다.

그 결과, 정말 약간의 센스를 요구하는 부분을 알 수 있었다.

현재 내가 작성한 코드에서는 재귀적으로 함수를 호출할 때 중복이 발생하고 있는데 return func(a, b / 2, c)의 값이 return되면 그 값을 변수에 저장함으로써 불필요한 중복 계산을 피하게끔 처리해줌으로써 그 중복을 해결해줄 수 있다.

아래는 수정한 코드이다.

#include <bits/stdc++.h>
using namespace std;

long long a, b, c, answer;

long long func(long long a, long long b, long long c) {
  if (b == 0) return 1;
  if (b == 1) return a % c;

  long long tmp = func(a, b / 2, c) % c;
  if (b % 2 == 0) {
    return tmp * tmp % c;
  } else {
    return tmp * tmp % c * a % c;
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> a >> b >> c;
  answer = func(a, b, c);
  cout << answer;

  return 0;
}

tmp라는 변수에 재귀함수 return값을 매 호출 시 마다 저장해주는 것을 확인할 수 있다.

실제로 결과도 성공이었다.

꼬롬 3스택의 문제는 정말 힘들었다.. 그래도 모듈러 연산, 재귀호출의 불필요한 연산 처리에 관한 점을 배울 수 있어서 굉장히 좋은 문제였던 것 같다.