📚 1182 - 부분수열의 합

부분수열의 합

이해

부분 수열의 합을 구하는 문제이다.
이와 같은 문제를 만났을 때는

• 순열 조합을 사용하면 된다.
• dfs를 사용하면 된다.

소스

조합

import sys
from itertools import combinations

read = sys.stdin.readline

n, s = map(int, read().split())

arr = list(map(int, read().split()))

result = 0

for i in range(1, n+1):
    check_data = combinations(arr, i)

    for c in check_data:
        if sum(c) == s:
            result += 1

print(result)

dfs1

import sys

read = sys.stdin.readline

n, s = map(int, read().split())

arr = list(map(int, read().split()))



result = []

cnt = 0

def dfs(idx):
    global cnt
    if len(result) > 0 and sum(result) == s:
        cnt += 1

    for i in range(idx, n):
        result.append(arr[i])
        dfs(i+1)
        result.pop()

dfs(0)

print(cnt)

dfs2

import sys

def function(cur, t):
    global cnt
    if N == cur:
        if t == S:
            cnt += 1
        return
    function(cur+1, t) # 다음 번째, 현재 나온 합
    function(cur+1, t+data[cur]) # 다음 번째, 현재 나온 합 + 현재 위치 숫자



N, S = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
cnt = 0
function(0, 0)
if S == 0:
    cnt -= 1
print(cnt)

결과를 보면 순열 조합이 dfs1보다 시간이 더 좋게 나온다.
다만, dfs2와 같이 사용할시, 마지막 위치에서 현재 구한 값이 S인지 쉽게 판단할 수 있다. (1번 -> 2번 ~ -> 5번, 2번 -> ~ -> 5번, 4번 -> ~ -> 5번)