사용자 도구

사이트 도구


ps:problems:boj:2087

암호문

ps
링크acmicpc.net/…
출처BOJ
문제 번호2087
문제명암호문
레벨골드 1
분류

meet in the middle

시간복잡도O(2^(n/2))
인풋사이즈n<=40
사용한 언어Python 3.11
제출기록171156KB / 1764ms
최고기록1764ms
해결날짜2023/08/18

풀이

  • 얼핏보면 복잡한 문제 같아보이는데, 이해하고 나면 그냥 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()

토론

댓글을 입력하세요:
K C E E A
 
ps/problems/boj/2087.txt · 마지막으로 수정됨: 2023/08/18 05:00 저자 teferi