[Algorithm] 백준 1182 부분수열의 합 python

백준 1182 부분수열의 합 링크

문제

N개의 정수로 이루어진 수열이 있을 때, 그 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하기

입력으로 N과 S가 주어지고, 다음 줄에 N개의 수열이 주어진다. 이 수열의 부분수열 중에서 합이 S가 되는 경우의 수를 고르면 된다.

어떻게 풀었지?

처음 보자마자는 어차피 N의 범위가 1<=N<=20이기 때문에 부분집합의 수가 2^n개니까 그래봤자 2^20이면 1,048,576. 그냥 전체 부분집합 구해서 다 더하는 완전 탐색으로 하면 될거라고 생각했다.

어디서 헤맸지?

딱히..?

Code

import sys
from itertools import combinations

def solve() :
    n,s = map(int,sys.stdin.readline().split())

    a = list(map(int,sys.stdin.readline().split()))

    count = 0

    for i in range(1,n+1) :
        sub = list(combinations(a,i))
        for c in sub :
            if sum(c) == s :
                count +=1
                
    print(count)


if __name__ == "__main__" :
    solve()

요새 최대한 파이써닉 한 코드를 짜고 싶다. 맨날 처음 언어 배웠던 c++처럼 썼었는데 다른 사람들 python 코드 보면 정말 간결하고 라이브러리도 잘 쓰고 잘 짜더라. itertool에 permutations랑 combinations는 완전탐색 할 때 정말 많이 쓰이는 것 같다.

다른 사람들 코드를 보면 dfs처럼 푼 분들도 많아서 그렇게도 한번 풀어봤다.

import sys

count  = 0

def dfs(idx,sum,n,s,a) :
    if idx >= n :
        return

    if sum+a[idx] == s   :
        global count
        count+=1

    dfs(idx+1,sum,n,s,a)
    dfs(idx+1,sum + a[idx],n,s,a) 


def solve() :
    n,s = map(int,sys.stdin.readline().split())

    global count
    count = 0

    a = list(map(int,sys.stdin.readline().split()))
    dfs(0,0,n,s,a)

    print(count)

if __name__ == "__main__" :
    solve()

해당 원소를 포함하는 경우, 안 포함하는 경우 가지를 쭉쭉 뻗어나가면서 재귀로 완전탐색을 돌리는 것 같다.