(Python/파이썬) - 백준(BOJ) 1182번 : 부분수열의 합

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

---

• 문제 : 

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

 

 

 

---

• 풀이 :

완전탐색으로 해결할 수 있는 문제였습니다.

 

처음에 문제를 잘못 이해햐여 연속되는 부분수열의 합을 구하는 문제인 줄 알고 

 

n1, n2, n3, n4 가 있다면

 

n1

n1, n2

n1, n2. n3

n1, n2, n3, n4

n2

n2, n3

n2, n3, n4

n3

n3, n4

n4

 

의 합을 구하게 구현하였는데 부분수열의 정의에는 "연속되는" 이라는 개념은 없다는 것을 깨닫고 다시 구현했습니다.

 

크기가 양수인 부분수열이기 때문에 크기를 의미하는 cnt 와 총 합인 s, 다음 시작한 인덱스 번호인 idx를 배개변수로 주었습니다. cnt가 0을 초과하고 s가 문제에서 요구하는 S와 같을 때 정답을 1씩 증가시켰으며 idx부터 N번째 원소까지 순회하며 재귀함수를 호출하게 하였습니다.

 

 

 

---

• 소스코드 : 

N,S  = map(int,input().split())
nums = list(map(int,input().split()))
answer = 0
def bt(s, idx, cnt):
    global answer,S
    if s == S and cnt > 0:
        answer += 1
    for i in range(idx, N):
        bt(s+nums[i], i+1, cnt + 1)
bt(0,0,0)
print(answer)