[BOJ] 1182 / 부분수열의 합 / Python 파이썬

[BOJ] 1182 / 부분수열의 합 / Python 파이썬

[BOJ] 1182 / 부분수열의 합 / Python 파이썬

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

1182번: 부분수열의 합

 

 

풀이

주어진 수열의 부분 수열의 합을 구하는 문제인데, 조합과 DFS 로 풀어보았다.

 

# 조합
from itertools import combinations

N, S = map(int, input().split())
nums = list(map(int, input().split()))

res = 0

for i in range(1, N+1):
    for comb in combinations(range(N), i):
        add = 0
        for c in comb:
            add += nums[c]
        if add == S:
            res += 1
print(res)

 

 

# DFS
N, S = map(int, input().split())
nums = list(map(int, input().split()))
res = 0


def DFS(idx, add):
    global N, S, res
    if idx == N:
        return

    add += nums[idx]

    if add == S:
        res += 1

    DFS(idx+1, add)
    DFS(idx+1, add-nums[idx])


DFS(0, 0)
print(res)

 

 

※DFS 풀이가 경우의 수가 더 적어, 측정된 시간이 더 짧았다. (효율적이다.)