BOJ 13277(큰 수 곱셈) 문제 풀이
08 Jul 2018 | PS FFT목차
참조
분류 | URL |
---|---|
문제 | BOJ 13277: 큰 수 곱셈 |
참조 라이브러리 | fft.h, conversion_library.h |
이 글에서 설명하는 코드 | 13277_큰 수 곱셈 |
개요
시간복잡도: $ O(N) $
공간복잡도: $ O(N) $
- N은 두 수의 길이 중 max값이다.
문제 풀이
풀이 자체는 어렵지 않다. 빠른 곱셈을 위해, FFT 를 쓰면 된다. 그게 이 문제의 풀이의 전부이다.
문제 자체가 데이터에 대한 전처리는 다음과 같은 것을 해주면 된다.
- reverse를 시켜준다. 큰 수 처리는 가장 낮은 자리수를 맨 앞에 두므로, reverse를 해야 한다.
- 곱셈을 할 경우 자리수가 최대 두 배 정도까지 늘어나므로 자리수를 두 배만큼 늘려 준다.
- 다시 reverse를 한다. 이 때 앞쪽의 0들은 출력하지 않도록 한다.
- 곱셈 결과가 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;
}
주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 못 믿겠다면, 저런 헤더 파일이 채점 사이트에 있을 것이라 생각하는가?