[Silver II] 부분수열의 합 - 1182

문제 링크

성능 요약

메모리: 31256 KB, 시간: 380 ms

분류

백트래킹, 브루트포스 알고리즘

문제 설명

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

입력

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

출력

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

---

풀이

아이디어

백트래킹의 아이디어를 가지고 모든 경우의 수를 완전탐색 하였다.
1. DFS함수에 시작값을 집어넣는다. (매개변수는 인덱스 번호임.)
2. 만약 들어온 매개변수 값이 탈출조건을 만나면 돌아간다.
3. 또한 이때까지 더해온 값 ss와 새로운 수열의 값 lst[current]를 계산하여 목표하는값 s를 만난다면 결과 값 (경우의 수)에 추가한다.
4. 두가지 방법으로 탐색을 진행하는데, 현재 인덱스의 값lst[current]를 포함시키는지와, 포함시키지 않는 방법으로 탐색한다.
5. 백트래킹을 시도하기 위해 결과값ss에서 탐색한 값을 빼준다.

이때 탐색된 트리의 최 하단은 $2^{n}$이다.

코드

n, s = map(int, input().split())
lst = list(map(int, input().split()))
result = 0
ss = 0

def dfs(current):
    global ss, result
    if current == n:
        return  # 탈출 조건
    
    if ss + lst[current] == s:
        result += 1
    
    dfs(current+1)
    
    ss += lst[current]
    dfs(current+1)

    ss -= lst[current]

dfs(0)
print(result)

---

회고

DFS를 구현할 때 재귀 이외에는 구현해본적이 없는데 반복문으로 재 구성해보는 연습을 해보면서 다양한 방식으로 알고리즘을 구성하는 방법을 배웠다.

오히려 재귀를 생각해내는 것보다 직관적이어서 그런지 조금 더 간단한 느낌이다.