사용자 도구

사이트 도구


ps:problems:boj:13277

큰 수 곱셈

ps
링크https://www.acmicpc.net/problem/13277
출처BOJ
문제 번호13277
문제명큰 수 곱셈
레벨브론즈 5
분류

고속 푸리에 변환

시간복잡도O(nlogn)
인풋사이즈n <= 300,000
사용한 언어Python
제출기록36260KB / 132ms
최고기록116ms
해결날짜2021/02/14

풀이

  • 큰 수의 곱셈을 계산하는 것은 카라츠바 알고리즘, FFT 알고리즘 등이 필요한 고급 알고리즘이지만, 파이썬을 비롯한 몇몇 언어들은 내부적으로 이것들이 이미 구현되어 있어서 그냥 가져다 쓰기만 한다.
    • 인풋의 크기가 똑같지만, 언어 제한이 걸려서 직접 구현해야만 하는 큰 수 곱셈 (2) 문제는 난이도가 플래티넘으로 책정되어 있다.
  • 그냥 단순히 인풋받고, int로 변환하고, 곱한뒤에 출력하는 것만으로도 통과가 가능하다. 이렇게 하면 5000ms 정도의 시간이 걸린다.
  • 그러나 좀 더 빠른 방법은 int가 아닌, decimal.Decimal로 변환해서 계산하는 것이다. 이렇게 하면 100ms 정도로 시간이 줄어든다!
  • 이것과 관련된 배경은 고속 푸리에 변환 (Fast Fourier Transform, FFT)에 소개했다. 둘다 내부적으로는 C모듈로 구현된것은 같지만, int 오브젝트가 좀더 복잡하게 구현되어 있고 카라츠바 알고리즘으로 곱셈 계산이 이루어지지만, Decimal 객체는 libmpdec 라이브러리로 처리되고 곱셈은 NTT로 이루어진다고 한다.

코드

"""Solution code for "BOJ 13277. 큰 수 곱셈".

- Problem link: https://www.acmicpc.net/problem/13277
- Solution link: http://www.teferi.net/ps/problems/boj/13277
"""

import decimal


def main():
    decimal.setcontext(
        decimal.Context(prec=decimal.MAX_PREC, Emax=decimal.MAX_EMAX))
    A, B = [decimal.Decimal(x) for x in input().split()]
    print(format(A * B, 'f'))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
N G N A E
 
ps/problems/boj/13277.txt · 마지막으로 수정됨: 2021/02/14 04:00 저자 teferi