사용자 도구

사이트 도구


ps:problems:boj:1067

이동

ps
링크https://www.acmicpc.net/problem/1067
출처BOJ
문제 번호1067
문제명이동
레벨플래티넘 2
분류

고속 푸리에 변환

시간복잡도O(nlogn)
인풋사이즈n <= 60,000
사용한 언어Python
제출기록49492KB / 444ms
최고기록444ms
해결날짜2021/02/13
태그

46단계

풀이

  • 고속 푸리에 변환 (Fast Fourier Transform, FFT)을 써서 합성곱을 구하는 전형적인 문제.
  • 수열 한개를 두번 이어 붙인 후, FFT로 다항식 곱셈을 해서 얻어지는 수열의, N-1부터의 N개 항이 우리가 원하는 합성곱이다.
    • 수열을 바꾸지 않고 그냥 다항식 곱셈을 해서 수열을 얻고, i번째 항과 N+i번째 항을 더하는 방식으로 합성곱 수열을 계산할 수도 있다.
  • 시간복잡도는 고속 푸리에 변환에 필요한 O(nlogn)

코드

"""Solution code for "BOJ 1067. 이동".

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

from teflib import fft

MAX = 100


def main():
    N = int(input())
    X = [int(x) for x in input().split()]
    Y = [int(x) for x in input().split()]

    res = fft.multiply(X + X, Y[::-1])
    print(max(res[N - 1:N + N - 1]))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
L X J R P
 
ps/problems/boj/1067.txt · 마지막으로 수정됨: 2021/05/05 16:33 저자 teferi