Golf Bot

• FFT를 이용해서 All possible sums를 찾는 전형적인 문제. 자세한 내용은 All possible sums 참고.
• 두번에 갈 수 있는 지가 아니라, 두번 이내에 갈 수 있는 지를 구하는 것이라는 점에.
  • 가장 간단한 처리법은 골프 봇이 칠수 있는 거리에 0도 추가한 뒤, 두번에 갈 수 있는지를 체크하는 것이다.
• 시간복잡도는 O(N+M+klogk). (k=max(d))
  • 실제 fft를 돌리는 데에 걸리는 시간은 배열의 길이인 N, M이 아닌, max(d)에 의해 결정된다는 점을 기억하자.

"""Solution code for "BOJ 10531. Golf Bot".

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

import sys
from teflib import fft


def main():
    N = int(sys.stdin.readline())
    k = [int(sys.stdin.readline()) for _ in range(N)]
    M = int(sys.stdin.readline())
    d = [int(sys.stdin.readline()) for _ in range(M)]
    max_d = max(d)

    f = [1] + [0] * max_d
    for k_i in k:
        if k_i <= max_d:
            f[k_i] = 1
    f_square = fft.multiply(f, f)
    answer = sum(1 for d_i in d if f_square[d_i] > 0)
    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.fft.multiply