사용자 도구

사이트 도구


ps:problems:boj:1208

부분수열의 합 2

ps
링크acmicpc.net/…
출처BOJ
문제 번호1208
문제명부분수열의 합 2
레벨골드 1
분류

Meet in the middle

시간복잡도O(2^(n/2))
인풋사이즈n<=40
사용한 언어Python
제출기록149996KB / 964ms
최고기록832ms
해결날짜2021/09/19

풀이

코드

"""Solution code for "BOJ 1208. 부분수열의 합 2".

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

Tags: [MeetInTheMiddle]
"""

import collections


def main():
    N, S = [int(x) for x in input().split()]
    nums = [int(x) for x in input().split()]

    first, second = [0], [0]
    for num in nums[:N // 2]:
        first.extend([num + x for x in first])
    for num in nums[N // 2:]:
        second.extend([num + x for x in second])
    second_counter = collections.Counter(second)

    answer = sum(second_counter[S - f] for f in first)
    if S == 0:
        answer -= 1
    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
K C F L L
 
ps/problems/boj/1208.txt · 마지막으로 수정됨: 2021/09/29 12:38 저자 teferi