[BOJ 1629] 곱셈

1) 문제 링크

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

2) 접근

일단 쌩계산은 python 같이 Big Integer가 아닌 이상 불가능. C++로 해결하려면 다음의 성질을 이용한 분할 정복을 해야한다고 생각했다.

자연수 p, q, r에 대하여 pXq를 r로 나눈 나머지는 (p를 r로 나눈 나머지)X(q를 r로 나눈 나머지)를 r로 나눈 나머지와 같다.

3) 풀이

#include <iostream>
using namespace std;

int a, b, c;

unsigned long long sq(unsigned long long num){ return num*num; }

unsigned long long solve(int cnt){
    if(cnt == 1) { return a % c; }

    if(cnt & 1){ return solve(cnt / 2) * solve(cnt / 2 + 1) % (unsigned long long)c; }
    else{ return sq(solve(cnt / 2)) % (unsigned long long)c; }
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> b >> c;
    cout << solve(b);
    return 0;
}

처음 작성한 코드다. 사실 이전에 한 번 내긴 했는데 함수 반환형을 int로 해서 에러가 날 거 같다는 생각이 들긴 했었다. 그것만 고쳐서 제출했다. sq 함수는 cnt가 짝수일 때 굳이 함수를 2번 호출하고 싶지 않아서 만들었다.

Master Theorem에서 cnt가 짝수인 경우 a=1, b=2, d=0이 되어 O(logn)이지만 cnt가 홀수인 경우 a=2, b=2, d=0이 되어 O(n)이라 24ms가 뜬 것 같다. 그래서 다른 분들의 풀이에서 A^B = (A^(B/2))*A라는 힌트를 얻어 코드를 개선해 홀짝 관계없이 O(logn)으로 코드를 작성했다.

#include <iostream>
using namespace std;

unsigned long long a, b, c;

unsigned long long sq(unsigned long long num){ return num*num; }

unsigned long long solve(int cnt){
    if(cnt == 1) { return a % c; }

    if(cnt & 1){ return (sq(solve(cnt / 2)) % c) * (a % c) % c; }
    else{ return sq(solve(cnt / 2)) % c; }
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> b >> c;
    cout << solve(b);
    return 0;
}

깔-끔

+(2021-08-12) 이 글을 작성했을 당시는 대학교 입학 전이었다. 그리고 입학 첫 학기에 수강한 ‘컴퓨터의 개념 및 실습’ 과목에서 이 문제와 솔루션을 그대로 다시 보게 되었다… 글 작성 당시에는 O(logn)으로 짜는 방법이 새로운 발상이었지만 지금은 익숙해졌다.

4) 피드백

qkrqotjd91님의 소스코드.
멋지다! 십진수를 이진수로 변환할 때의 원리를 이용한 것으로 보인다. 시간복잡도만 보면 O(logN)으로 다를 게 없으나 확실히 깔끔하다.