[백준/Python] 1182 부분수열의 합

 

📌 문제 탐색하기

• N개의 정수로 이루어진 수열 (1 ≤ N ≤ 20)
  • 이 수열의 크기가 양수인 부분 수열 중 그 수열의 원소의 합이 S(|S| ≤ 1,000,000)가 되는 경우의 수
• 부분 수열의 개념
  • 주어진 수열에서 각 원소는 포함되거나 포함되지 않을 수 있다. 즉, 부분 수열의 모든 경우를 탐색하기 위해 2^N-1(빈 수열 제외)개의 부분 수열을 확인해야 한다.

N의 크기가 최대 20으로, 최대 길이인 경우에 부분 수열의 개수는 2^20 - 1이므로 모든 부분 수열에 대해 합을 구해 주어진 S와 비교해보아도 시간 내에 문제를 풀이할 수 있다.

모든 부분 수열의 경우를 탐색하기 위해 재귀를 사용할 수 있다.

---

📌 코드 설계하기

1. N과 S를 입력받는다.
2. 수열의 원소들 seq 리스트로 입력받는다.
3. 모든 원소의 합이 S인 부분 수열의 개수를 저장할 변수 count를 0으로 초기화한다. 
4. 재귀 함수 calc_subseq_sum를 통해 n번째 위치의 원소를 부분 수열에 포함시키는 경우, 아닌 경우로 나누어 재귀적으로 부분 수열의 합을 구한다▶ 해당 과정에서 현재 선택된 원소 개수를 같이 매개변수로 넘겨서, 빈 부분 수열의 경우는 확인하지 않도록 한다.
5. 재귀 함수가 실행되는 동안, 부분 수열의 합을 S와 비교하여 합계가 정확히 S이 경우 count를 1 증가 시킨다.
6. count를 출력한다.

 

---

📌 정답 코드

def calc_subseq_sum(idx, cur_sum, selected_cnt): # 현재 원소 index, 현재까지의 합
    global count
    if idx == N:
        if cur_sum == S and selected_cnt:
            count += 1
        return

    calc_subseq_sum(idx+1, cur_sum + seq[idx], selected_cnt+1)
    calc_subseq_sum(idx+1, cur_sum, selected_cnt)
    

N, S = map(int, input().split())
seq = list(map(int, input().split()))
count = 0
calc_subseq_sum(0, 0, 0)

print(count)