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

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

1182번: 부분수열의 합

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	54390	25060	16181	44.322%

 

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

5 0
-7 -3 -2 5 8

 

예제 출력 1

1

 

---

문제를 살펴보면 순열로 미리 N개의 정수로 이루어진 수열의 모든 경우의 수를 가지고 합이 S인 경우를 세면 됩니다.
하지만 Backtracking을 연습하는 차원에서 순열 라이브러리를 사용하지 않고 풀어보겠습니다.

이전에 제가 올렸던 Backtracking 포스팅의 문제를  풀어 보셨다면 너무나 쉽게 풀리는 문제입니다.
N과 M 문제를 안 푸셨다면 먼저 푸시는 것을 추천드립니다.
https://great-park.tistory.com/category/Algorithm/BackTracking

'Algorithm/BackTracking' 카테고리의 글 목록

해당 문제는 탐색의 제약 조건은 중복을 제외한다는 점만 신경쓰면 되고, 탐색 종료 조건에서 합이 S인지만 확인하면 됩니다.

 

from sys import stdin
input = stdin.readline
N, S = map(int, input().split())
num = list(map(int, input().split()))
cnt = 0
ans = []


def solve(start):
    global cnt
    if sum(ans) == S and len(ans) > 0:
        cnt += 1

    for i in range(start, N):
        ans.append(num[i])
        solve(i+1)
        ans.pop()


solve(0)
print(cnt)

여기서도 입력받은 수열을 사용해야 하므로, 탐색의 depth와 같은 역할을 하는 start부터 다음 탐색을 진행하고 있습니다.