암호문

• 얼핏보면 복잡한 문제 같아보이는데, 이해하고 나면 그냥 Subset Sum Problem이다. 합이 2,000,000,000 으로 매우 크므로 DP로 구할수는 없지만, 대신 n이 작기 때문에 meet in the middle 을 써서 구해주면 된다.
• 합이 K가 되는 부분집합의 존재여부만 찾는게 아니라, 그러한 부분집합을 실제로 구해야 한다. 왼쪽 절반과 오른쪽 절반의 부분집합 합들을 {합: 부분집합} 형태의 딕셔너리로 저장해야 하는데, 부분집합을 bitset으로 저장해야 속도와 메모리를 줄일수 있다.
• 이렇게 해도 python에서는 메모리가 살짝 부족한데 (pypy로는 통과), 왼쪽절반에 대해서만 딕셔너리에 저장하고, 오른쪽 절반은 그냥 백트래킹하면서 찾아주면 python에서도 통과된다.
• 시간복잡도는 O(2^(n/2))

"""Solution code for "BOJ 2087. 암호문".

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

Tags: [mitm]
"""

from teflib import backtracking


def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    K = int(input())

    bit_by_subset_sums = {0: 0}
    for i, a_i in enumerate(a[: n // 2], start=1):
        for sum_, bit in list(bit_by_subset_sums.items()):
            bit_by_subset_sums[sum_ + a_i] = bit | (1 << (n - i))

    pos = n - n // 2 - 1
    for sum_, inds in backtracking.subsets(
        a[n // 2 :], 0, lambda s, num: None if s + num > K else s + num
    ):
        if (left_bit := bit_by_subset_sums.get(K - sum_)) is not None:
            right_bit = sum(1 << (pos - i) for i in inds)
            answer = format(left_bit + right_bit, f'0{n}b')
            print(answer)
            break


if __name__ == '__main__':
    main()

• Dependency: teflib.backtracking.subsets