백준 1182 부분수열의 합 -python
문제
- 브루트 포스 문제
문제풀이
- 재귀 함수 종료조건을 인덱스 범위를 벗어난 경우
- 이때 부분수열의 더한 값이 s와 같으면 return
code
- 재귀를 이용한 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def f(idx, d):
global res
if(idx >= n):
if(s == d):
res += 1
return
else:
# 원소를 포함하는 경우
f(idx+1, d+arr[idx])
# 원소를 포함하지 않는 경우
f(idx+1, d)
n, s = map(int, input().split())
arr = list(map(int, input().split()))
res = 0
f(0,0)
# s가 0인, 즉 공집합인 경우에는 정답에서 -1을 해줌
if(s):
print(res)
else:
print(res - 1)
- 멱집합(powerset)을 이용한 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def powerset(arr):
arr_size = len(arr)
res = []
for i in range(2**arr_size):
# str class의 bin, zfill로 binary값을 이용해서 구하기
check = bin(i)[2:].zfill(arr_size)
subset = []
for j in range(arr_size):
if(check[j] == '1'):
subset.append(arr[j])
res.append(subset)
return res
n, s = map(int, input().split())
arr = list(map(int, input().split()))
arr = powerset(arr)
cnt = 0
for i in arr:
if(sum(i) == s):
cnt += 1
print(cnt if s else cnt-1)
