난이도

Silver 2

풀이 참고 유무

x

막힌 부분

x

문제

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

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입력

5 0
-7 -3 -2 5 8

예제 출력

1

문제 검토

조건을 만들어가고 회수하며 순열처럼 경우의 수들을 구하는 점에서 백트랙킹 문제라고 할 수 있다.

풀이(python)

Python

import sys
input=sys.stdin.readline
n,s=map(int,input().split())
num=list(map(int,input().split()))
for x in range(len(num)):
    num[x]=[num[x],False,x]
cnt=0
tmp=[]
def dfs(idx,depth,result,beforeidx,start):    
    global cnt
    if not start and result==s:                
        cnt+=1             
    start=False
    if depth==n:
        return
    for x in range(idx,len(num)):
        if not num[x][1] and beforeidx<=num[x][2]:
            result+=num[x][0]
            num[x][1]=True                                      
            tmp.append(num[x][0])            
            dfs(idx+1,depth+1,result,num[x][2],start)            
            tmp.pop()
            num[x][1]=False
            result-=num[x][0]
dfs(0,0,0,0,True)            
print(cnt)

아이디어:

#리스트 순서대로 백트랙킹을 진행한다.abs
#True,False로 사용 여부 체크
#0이 되면 cnt+1 부분 수열들을 다 찾는 것이기 때문에 return 하지는 않는다.
#깊이가 전체 수열의 길이까지 왔는데 0이 되지 않았으면 return

시간복잡도

#정수의 범위가 꽤 큰데 시간 초과가 나지 않을지 모르겠다.

자료구조

#2차원 리스트:정수 모임과 방문체크

걸린 시간

32:12

총평

기본적인 백트랙킹 문제이다.