타겟 넘버

• Subset sum 문제처럼, 각 숫자의 크기 제한이 없다면 NP가 되는 문제이지만, 제한이 있어서 DP로 풀 수 있다.
  • 왜 사이트에서는 BFS/DFS로 분류되어 있는지 모르겠다.

• DP[n][t]을 numbers[0]부터 numbers[n-1]까지를 써서 합이 t가 되는 경우의 수라고 하면
  • DP[n][t] = DP[n-1][t-numbers[n]] + DP[n-1][t+numbers[n]] 이 된다.
• m을 가능한 숫자의 최대값(=50) 이라 하면, n개의 숫자의 합은 [-n*m, n*m] 범위에 있으니까, DP 테이블의 크기는 n*(2*n*m)으로 잡아서 처리하면 된다. 이렇게 되면 테이블 한칸을 채우는데 O(1)이니까 총 시간 복잡도는 O(n*n*m).
• 실제 구현할 때는, 테이블 전체를 유지할 필요 없이 최근 2행만 유지하면서 업데이트하면 된다.
• 또한 DP[n-1][t]가 0이 아닌 곳에서만 DP[n][t±numbers[n]]를 업데이트 해주면 되고, DP[n-1][t]가 0이 아닌 곳의 갯수는 2*n*m에 비해서 많이 적기 때문에, 배열 대신에 set을 쓰는 것이 유리하다.
• 숫자의 갯수가 최대 20개라서, O(2^n)으로 완전 탐색을 해도 풀이는 가능하다..

"""Solution code for "Programmers 43165. 타겟 넘버".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/43165
- Solution link: http://www.teferi.net/ps/problems/programmers/43165
"""

import collections


def solution(numbers, target):
    dp_cur = {0: 1}
    for number in numbers:
        dp_cur, dp_prev = collections.defaultdict(int), dp_cur
        for result, count in dp_prev.items():
            dp_cur[result + number] += count
            dp_cur[result - number] += count
    return dp_cur[target]