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

문제 (링크)

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

1182번: 부분수열의 합

 

나의 풀이

import sys
from itertools import combinations

input = sys.stdin.readline
n, s = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0
for i in range(1, n+1):
    comb = combinations(arr, i)

    for x in comb:
        if sum(x) == s:
            cnt += 1

print(cnt)

코드 설명 및 풀이법

파이썬의 combinations 함수를 호출해 배열에서 뽑을 수 있는 모든 조합을 구해준다.

 

해당 조합들의 총합이 구하고자 하는 합과 같다면 해당 조합의 숫자를 세준다.

 

브루트포스 방식을 사용한 것이라고 볼 수 있다.

 

다른 풀이

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
    
    # 현재 arr[idx]를 선택한 경우의 가지
    subset_sum(idx+1, sub_sum)

    # 현재 arr[idx]를 선택하지 않은 경우의 가지
    subset_sum(idx+1, sub_sum - arr[idx])

subset_sum(0, 0)
print(cnt)

코드 설명 및 풀이법

재귀함수와 백트래킹을 활용한 풀이법이다.

 

0번째 인덱스부터 시작해 n-1번째 인덱스까지 각 원소의 값들을 넣고, 해당 값을 지금까지 구해온 sub_sum에 더하는 경우와 더하지 않는 경우를 각 가지로 나누어 재귀함수를 호출한다.

 

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