티스토리 뷰
https://www.acmicpc.net/problem/13277
13277번: 큰 수 곱셈
첫째 줄에 정수 A와 B가 주어진다. 두 정수는 0보다 크거나 같은 정수이며, 0을 제외한 정수는 0으로 시작하지 않으며, 수의 앞에 불필요한 0이 있는 경우도 없다. 또한, 수의 길이는 300,000자리를
www.acmicpc.net
FFT의 대략적인 개념은 알고 있었지만 (그냥 다항식 곱셈 빨리한다는 정도....) FFT를 이해하고 적용시켜본 문제입니다.
FFT 개념은 아래의 글을 참고하였습니다.
https://ko.wikipedia.org/wiki/%EA%B3%A0%EC%86%8D_%ED%91%B8%EB%A6%AC%EC%97%90_%EB%B3%80%ED%99%98
고속 푸리에 변환 - 위키백과, 우리 모두의 백과사전
FFT는 여기로 연결됩니다. 다른 뜻에 대해서는 FFT (동음이의) 문서를 참고하십시오. 고속 푸리에 변환(高速 푸리에 變換, 영어: fast Fourier transform, FFT, 문화어: 고속푸리예변환)은 이산 푸리에 변환
ko.wikipedia.org
https://m.blog.naver.com/kks227/221633584963
고속 푸리에 변환(Fast Fourier Transform) (수정: 2019-09-05)
안녕하세요. 이번에 쓸 주제는 나름 유명한데 제가 의욕이 안 서서 굉장히 오랜 시간 동안 미뤄왔던 주제입...
blog.naver.com
각 숫자를 10^k 꼴의 다항식으로 생각할 수 있고, FFT 적용 시 각 항별 연산 결과가 그대로 저장되므로 10진수로 합칠 때 올림을 계산해주어야 합니다. 그리고 i번쨰 index 값이 10^i 의 계수인 것 또한 주의해야 합니다.
ex. 99 * 99 => 81의 결과가 계산 중간에 나오게 되므로 8을 올려주어야 한다.
코드는 다음과 같습니다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 2668 숫자고르기 C++ (0) | 2022.03.15 |
|---|---|
| 백준 1067 이동 C++ (0) | 2022.03.05 |
| 백준 1708 볼록 껍질 (0) | 2022.03.04 |
| 백준 4991 로봇 청소기 C++ (0) | 2022.03.01 |
| 백준 2151 거울 설치 C++ (0) | 2022.02.22 |