sgchoi5   2년 전

안녕하세요.

알고리즘 문제 해결 전략에 나오는 카라츠바 알고리즘으로 풀어 봤는데, 시간 초과로 나오네요.

책에 있는 시간 복잡도 값으로 계산해보니 (nlg3 ==1.585

n 이 300,000 이면 대략 5억 (479,995,525) 이고, 2 초로는 안 되는게 맞네요.

이 문제 푸신 분들은 어떤 방식으로 해결하신 건가요? =_=

baekjoon   2년 전

FFT

sgchoi5   2년 전

FFT 로 하면 O(nlogn) 으로 되는 거군요.  : )

kks227   2년 전

후... 이거 제가 FFT를 거지같이 짜서 각 계수를 한자리씩 끊으니까 시간 초과가 나길래 두자리, 세자리, 네자리... 이렇게 확장시켰던 기억이 나네요.

댓글을 작성하려면 로그인해야 합니다.