[백준 - Python] 1182. 부분수열의 합 (완전 탐색)

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

1182번: 부분수열의 합

 

코드

from itertools import combinations

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

cnt = 0
for i in range(1, n+1):
    com = list(combinations(seq, i))
    for j in range(len(com)):
        S = sum(com[j])
        if S == s:
            cnt += 1

print(cnt)

 

수열의 부분 수열 중 원소를 다 더한 값이

입력으로 주어지는 S가 되는 경우의 수를 구해야 했기 때문에

itertools  라이브러리의 조합 함수를 활용해

1 부터 n개를 선택하는 경우를 전부 확인하며

그 조합의 합이 S가 되는 경우를 구하면 되겠다고 생각했다.

 

생각대로 구현했고 통과했다.

 

 

다른 풀이

조합을 사용한 풀이 말고

백트래킹과 재귀함수를 활용한 풀이도 있다.

import sys
input = sys.stdin.readline

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

cnt = 0

def subset_sum(idx, sub_sum):
    global cnt

    if idx >= n:
        return

    sub_sum += arr[idx]

    if sub_sum == s:
        cnt += 1

    subset_sum(idx+1, sub_sum)
    subset_sum(idx+1, sub_sum - arr[idx])

subset_sum(0,0)
print(cnt)

 

0번째 인덱스부터 시작해 n-1번째 인덱스까지 각 원소의 값들을 넣고,

해당 값을 지금까지 구해온 sub_sum에

더하는 경우와, 더하지 않는 경우로 나누어 재귀함수를 호출한다.

 

각 재귀함수에서

sub_sum이 구하고자 하는 s와 같다면 전역변수 cnt에 1을 더해주면서 갯수를 세어준다.

 

 

조합 풀이보다는 재귀함수와 백트래킹을 사용한 풀이가 더 빨랐다.

 

 

 

참고 자료

https://seongonion.tistory.com/98