====== Golf Bot ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>
  * Dependency: [[:ps:teflib:fft#multiply|teflib.fft.multiply]]

{{tag>BOJ ps:problems:boj:플래티넘_2}}