[알고리즘|파이썬] 백준 1182 부분수열의 합

문제 링크: https://www.acmicpc.net/problem/1182

📌 문제 탐색하기

시간 제한: 2초
메모리 제한: 256 MB

구해야 하는 정답

N개의 정수가 주어지고, 이 N개로 만들 수 있는 부분수열 중 합이 S인 개수를 구하는 문제이다.

예를 들어, {1, 2, 3} 의 부분수열은 총 7개이고, 이들의 합은 다음과 같다:

{1} -> 1

{2} -> 2

{3} -> 3

{1, 2} -> 3

{1, 3} -> 4

{2, 3} -> 5

{1, 2, 3} -> 6

 

이때 모든 부분수열을 구하여 합을 계산해보는 방식으로, 즉 완전 탐색으로 문제를 접근해도 되는지 고려해봐야 한다.

N개의 정수로 만들 수 있는 부분수열은 2^N - 1 개이다.

 

nCn+nCn-1+…+nC1 = 2^n - 1

 

문제에서 N의 범위를 1 ≤ N ≤ 20 로 주었으므로,

2^1 ≤ 2^N ≤ 2^20 = 1,048,576, 주어진 시간 2초 안에 사용할 수 있다.

참고) 1초 => 약 1억
- 2^20 = 1,048,576
- 2^26 = 67,108,864 (1억에 가장 가까운 2^n)
- 2^30 ‎ = 1,073,741,824

 

주어진 N개의 숫자로 부분합 전체를 만들어 합이 S와 같은 것이 몇개인지 세면 된다.

---

📌 코드 설계하기

1. 문제의 Input N, S, N개의 정수를 받음

2. count = 0으로 초기화

3. 주어진 N개의 수로 combinations로 부분합 생성

• nCn, nCn-1, … , nC1
• 코드로 표현할때 주의사항!
  • range(1, n+1) => (1  ≤ i  < n+1) 

4. 부분합의 합이 S와 동일하다면 count++

5. count 출력

 

---

📌 정답 코드

import itertools

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

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

for i in range(1, n+1):
    comb = itertools.combinations(nums, i)
    for c in comb:
        if sum(c) == s:
            count += 1

print(count)