[1182] 부분수열의 합

 

백준 Silver II | 1182 | Python | 문제 링크

문제 설명

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

입출력 예

입력	출력
5 0 -7 -3 -2 5 8	1

 

나의 풀이

풀이 1

import sys
input = sys.stdin.readline

def backtrack(idx, total):
    global count
    if idx == n:
        if total == s:
            count += 1
        return
    backtrack(idx + 1, total + nums[idx])
    backtrack(idx + 1, total)

n, s = map(int, input().split())
nums = list(map(int, input().split()))
count = 0
backtrack(0, 0)
if s == 0:
    count -= 1
print(count)

풀이 설명

각 원소를 포함하거나 제외하는 두 갈래로 재귀를 진행한다. 모든 원소를 결정하면 합이 S인지 확인한다.

• backtrack(idx + 1, total + nums[idx]) — 현재 원소 포함
• backtrack(idx + 1, total) — 현재 원소 제외
• if s == 0: count -= 1 — S가 0이면 빈 부분수열(합 = 0)도 카운트되므로 1을 뺀다.

풀이 2

import sys
input = sys.stdin.readline

n, s = map(int, input().split())
nums = list(map(int, input().split()))
count = 0

for mask in range(1, 1 << n):
    total = sum(nums[i] for i in range(n) if mask & (1 << i))
    if total == s:
        count += 1

print(count)

풀이 설명

N개의 원소는 각각 포함/제외 두 가지 상태를 가지므로 부분수열의 총 경우는 2^N가지다. 비트마스크로 각 경우를 표현한다.

• mask의 i번째 비트가 1이면 nums[i]를 포함한다는 의미다.
• range(1, 1 << n) — 0(빈 집합)을 제외하고 시작하므로 S == 0 보정이 필요 없다.