Gorio Tech Blog search

BOJ 13277(큰 수 곱셈) 문제 풀이

08 Jul 2018 | PS FFT

목차

참조

분류 URL
문제 BOJ 13277: 큰 수 곱셈
참조 라이브러리 fft.h, conversion_library.h
이 글에서 설명하는 코드 13277_큰 수 곱셈

개요

시간복잡도: $ O(N) $

공간복잡도: $ O(N) $

  • N은 두 수의 길이 중 max값이다.

문제 풀이

풀이 자체는 어렵지 않다. 빠른 곱셈을 위해, FFT 를 쓰면 된다. 그게 이 문제의 풀이의 전부이다.

문제 자체가 데이터에 대한 전처리는 다음과 같은 것을 해주면 된다.

  1. reverse를 시켜준다. 큰 수 처리는 가장 낮은 자리수를 맨 앞에 두므로, reverse를 해야 한다.
  2. 곱셈을 할 경우 자리수가 최대 두 배 정도까지 늘어나므로 자리수를 두 배만큼 늘려 준다.
  3. 다시 reverse를 한다. 이 때 앞쪽의 0들은 출력하지 않도록 한다.
  4. 곱셈 결과가 0인 경우 따로 0을 출력하도록 예외처리를 해 준다.

위의 사항만 주의하면, 입력받고, FFT를 적용하고, 출력하는 것이 끝이다.

구현

입출력이 조금 많으므로, string과 cin을 사용할 것이라면

ios::sync_with_stdio(false);
cin.tie(NULL);

를 해주자.

#include "../library/conversion_library.h"
#include "../library/fft.h"

int main_13277() {
    ios::sync_with_stdio(false);    cin.tie(NULL);
    string a, b;
    cin >> a >> b;
    vector<int> A = string_to_vi(a);
    vector<int> B = string_to_vi(b);
    reverse(A.begin(), A.end());	reverse(B.begin(), B.end());

    vector<int> ret = multiply(A, B);

    int i = 0;
    while (i < ret.size()) {
        if (ret[i] >= 10) {
            if (i == ret.size() - 1)
                ret.push_back(ret[i] / 10);
            else
                ret[i + 1] += ret[i] / 10;
            ret[i] %= 10;
        }
        ++i;
    }

    reverse(ret.begin(), ret.end());

    bool start = false;
    for (auto elem : ret) {
        if (elem)start = true;
        if (start)cout << elem;
    }
    if (!start)cout << '0';

    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 못 믿겠다면, 저런 헤더 파일이 채점 사이트에 있을 것이라 생각하는가?

Related Posts