부분수열의 합 1182번 백준

문제:www.acmicpc.net/problem/1182

1182번: 부분수열의 합

이 문제는 기존의 방식으로 모든 가능한 수열의 경우를 다 확인하는 식으로 코딩했었다.

 

import sys
N,S=map(int,sys.stdin.readline().rstrip().split())
li = list(map(int,sys.stdin.readline().split()))
passing=[False]*(N+1)
ans=[]
cnt=0
def func(ans,celi,aim,sum):
    global cnt,S
    if celi==aim:
        return
    for i in range(N):
        if not ans:
            passing[i]=True
            ans.append(i)
            sum+=li[i]
            if li[i]==S:
                cnt+=1
            func(ans,celi+1,aim,sum)
            sum-=li[i]
            ans.pop()
            passing[i]=False
        else:
            if not passing[i] and ans[-1]<i:
                passing[i]=True
                ans.append(i)
                sum+=li[i]
                if sum==S:
                    cnt+=1
                func(ans,celi+1,aim,sum)
                sum-=li[i]
                ans.pop()
                passing[i]=False
func(ans,0,N,0)
print(cnt)

처음에는 ans에 값이 없으므로 if not ans: 를 통해 값을 집어 넣고 다 더한 값이 S가 되는지 확인한다.

그리고 ans에 값이 존재한다면 그 뒤 나머지 수열을 생성하면서 S가 가능한지 확인하고 갯수를 갱신한다.

하지만 이 코드는 시간면에서 다소 아쉬운 코드였다. 

그래서 다른 분들의 코드를 봤다.

import sys
input = sys.stdin.readline
def dfs(idx, sum):
    global cnt
    if idx >= n:
        return
    sum += s_[idx]
    if sum == s:
        cnt += 1
    dfs(idx + 1, sum - s_[idx])
    dfs(idx + 1, sum)
n, s = map(int, input().split())
s_ = list(map(int, input().split()))
cnt = 0
dfs(0, 0)
print(cnt)

참고:https://pacific-ocean.tistory.com/306

[백준] 1182번(python 파이썬)

코드의 전체적인 흐름은 비슷하다. 하지만 이제 재귀부분에서 나의 코딩의 경우 초기값의 유무에 따른 if,else와 현재 그 값을 지났는지 안 지났는지 확인하는 부분에서 시간에 대한 소모가 많이 일어났을 것 같다.

순전히 각 원소가 포함되는 경우 포함되지 않는 경우 2가지의 경우를 각각 따져보면 되므로 

 

dfs(idx + 1, sum - s_[idx])
dfs(idx + 1, sum)
 

N,S = map(int,input().split())
ar = list(map(int,input().split()))
ans=0
for i in range(1,1<<N):
    sum=0
    for k in range(N):
        if i&(1<<k):
            sum+=ar[k]
    if sum==S: ans+=1
 
print(ans)

첫 번째 for문의 의미는 다음과 같다.

 

5 0
-7 -3 -2 5 8