[BOJ/python]1182번 부분수열의 합

백준 1182번 부분수열의 합 파이썬

문제 링크 - https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

부분수열은 연속할 필요 없이 주어진 수열에서 원소를 중복 없이 선택하면 된다. 즉, 주어진 수열의 순서가 바뀌어도 똑같은 답을 갖게 된다.

처음에는 백트래킹으로 시도했다. 전체 수열에서 원소를 선택하는 경우와 선택하지 않는 경우를 나누어 탐색한다. 하지만 DFS 도중에 가지치기 되는 경우가 없기 때문에 사실상 완전 탐색이다.

조금 더 효율적인 방법이 없을까 고민하다가 dp로도 풀어봤다.

1. 백트래킹 풀이

• 배열의 인덱스를 인자로 하는 DFS 함수를 통해 백트래킹을 구현한다.
• 현재 인덱스의 값을 합에 더하거나 더하지 않는 경우에 대하여 재귀를 수행한다.
• 현재 인덱스가 배열의 길이와 같다면 반환한다.

1.1 백트래킹 풀이 코드

N, S = map(int, input().split())
arr = list(map(int, input().split()))
tmp=0
sol = 0

def DFS(index):
    global tmp, sol
    if index == N :
        return

    if tmp + arr[index] == S:
        sol +=1

    DFS(index+1)
    
    tmp += arr[index]
    DFS(index+1)
    
    tmp -= arr[index]

DFS(0)
print(sol)

2. dp 풀이

냅색 문제를 푸는 방식과 유사하다.

• 딕셔너리에 부분수열의 합과 그 개수를 저장한다.
• 이전 인덱스까지 만들어진 부분수열의 합(a)에 현재 인덱스의 값(b)을 더하고 해당 값(a+b)이 이미 딕셔너리에 있다면 딕셔너리에서 a+b의 값을 a의 값으로 저장한다.
• (ex. 이전 인덱스까지 3을 2개 만들 수 있었고, 현재 인덱스의 값이 2라면, 5를 만들 수 있는 총 개수는 3의 개수와 같은 2이다.)

2.1 dp 풀이 코드

from collections import defaultdict
N,S = map(int, input().split())
L = list(map(int, input().split()))

dict = defaultdict(int)

for i in range(N):
    num = L[i]    
    candidate=defaultdict(int)
    candidate[num]=1

    for past in dict:
        candidate[num+past] += dict[past]    
  
    for c in candidate:   
        dict[c]+=candidate[c]
    
print(dict[S])