5.4 부분집합의 합 구하기 - DP

이번에는 지난번에 구현했던 재귀 호출을 DP로 바꿔본다.

DP의 접근 법은 상향식으로 문제를 풀어가면서 중간결과를 2차원 배열에 저장하는 것이다.

2차원 배열에 저장될 값은 각 집합의 첫(i+1) 개의 원소로 구성된 집합에 대해서 합이 j(0 <=j <=X)인 부분집합이 있는지에 대한 참/거짓의 값이다.

 

첫 번째 열은 무조건 참이 됨. 공집합인 부분집합 원소의 합은 언제나 0이기 때문.

첫 번째 행의 경우 집합과 j의 값이 같은 경우만 True, 다르면 False 값을 넣는다.

그 외의 조건은 다음과 같다.

1. 바로 위쪽 셀이 T면, 해당 셀도 T.

2. 그 외에는 (i-1, j-v) 셀의 값을 (i, j)로 복사.

위의 조건을 코드로 옮기면 다음과 같다.

 

def solve_dp(ar, n, x):
    subsum = [[False for _ in range(n)] for __ in range(x + 1)]

    for i in range(n):
        subsum[i][0] = True

    for j in range(1, x + 1):
        if ar[0] == j:
            subsum[0][j] = True
        else:
            subsum[0][j] = False

    for i in range(1, n):
        v = ar[i]
        for j in range(1, x + 1):
            if j < v:
                subsum[i][j] = subsum[i - 1][j]
            elif subsum[i - 1][j]:
                subsum[i][j] = True
            else:
                subsum[i][j] = subsum[i - 1][j - v]

    return subsum[n - 1][x]


if __name__ == '__main__':
    ar = list(map(int, input().split()))
    n = len(ar)
    x = int(input())
    print(solve(ar, n, x))

생각보다 로직이 복잡하다. 기존에 했던 것들에 비해.

j-v 값을 가져오는 게 좀 핵심인 듯..