[파이썬(Python)] 백준 1182번 부분수열의 합

 

 

백준 1182번: 부분수열의 합

문제 바로 가기

---

📌 문제

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

입력

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

출력

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

 

 

 

 

 

 

 

 

 

 

📝 문제 분석

 

 

이 문제는 N개의 정수로 이루어진 수열이 주어졌을 때, 크기가 1 이상인 부분수열 중에서 원소들의 합이 S가 되는 경우의 수를 구하는 문제입니다.

 

 

 

✅ 문제 조건

• 부분수열의 크기는 최소 1개 이상이어야 합니다. → 공집합은 제외
• 부분수열의 합이 S인 경우만 세야 합니다.
• N의 범위가 최대 20이므로 모든 부분수열을 탐색하는 완전탐색(Brute Force) 방법이 가능합니다. 

 

 

 

 

 

 

 

 

 

 

💡 해결 아이디어

 

문제를 해결하기 위해 부분수열을 생성하고 그 합이 S가 되는 경우를 찾아야 합니다. 이 과정을 효과적으로 구현하기 위해 비트마스크(Bitmask)를 사용합니다. 

 

 

 

 

 

📕 비트마스크(Bitmask)란?

 

비트마스트란 정수의 이진수 표현을 이용하여 특정 원소를 선택하거나 제외하는 기법입니다. 즉, 각 원소를 선택할지(1) 또는 선택하지 않을지(0)를 비트로 표현하는 방식입니다.

 

 

 

✅ 예제: N = 3이고 원소 집합이 {a, b, c}일 때 

비트마스크 값	포함된 원소
000	공집합 (X)
001	{c}
010	{b}
011	{b, c}
100	{a}
101	{a, c}
110	{a, b}
111	{a, ,b ,c}

이진수에서 1이 들어간 위치의 원소만 선택하면 부분집합을 만들 수 있습니다. 

 

 

 

 

 

 

 

 

 

 

🚀 해결 과정

 

 

 

1️⃣ Step 1: 가능한 모든 부분수열 만들기

 

부분수열(Subset)이란?

• N개의 정수 중 일부를 선택하는 방법
• 각 원소를 선택할 수도 있고 선택하지 않을 수도 있습니다.

 

 

✅ 비트마스크를 활용한 부분수열 생성

for bitmask in range(1, 1 << N):  # 공집합(000)은 제외
    subset = []
    
    for i in range(N):
        if bitmask & (1 << i):  # i번째 원소가 포함되었는지 확인
            subset.append(arr[i])

• 1 << N → 2^N을 의미합니다.
• bitmask & (i << i) → i번째 원소가 포함되어 있는지 확인합니다.
• 예를 들어, bitmask = 5 (101)이면 a(1), X, c(1)이므로 선택된 원소는 [a, c]입니다. 

 

 

 

 

 

 

 

2️⃣ Step 2: 부분수열의 합이 S인지 확인

 

각 부분수열의 합을 구한 뒤 S와 같다면 카운트합니다. 

if sum(subset) == s:	# 부분수열의 합이 S인지 확인
            cnt += 1	# 카운트 증가

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

def sovle():
    cnt = 0
    for bitmask in range(1, 1 << n):
        subset = []

        for i in range(n):
            if bitmask & (1 << i):
                subset.append(arr[i])
    
        if sum(subset) == s:
            cnt += 1
    return cnt

n, s = map(int, input().split())
arr = list(map(int, input().split()))

cnt = sovle()
print(cnt)

 

Algorithm/백준/Silver/1182. 부분수열의 합 at main · kuun1000/Algorithm