[Python | 1182] 부분수열의 합

https://www.acmicpc.net/problem/1182

---

문제 설명

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

 

📌 시간 제한: 2초

---

입력

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

---

출력

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

---

문제 접근

이 문제는 크기가 N인 수열에서, 합이 S가 되는 부분수열의 개수를 찾는 문제다. 처음 문제를 봤을 때, 부분수열을 직접 생성해서 합을 비교하는 방식이 떠올랐다. 하지만 문제 조건에서 공집합을 제외해야 한다는 점을 고려해야 했다.

완전 탐색을 할 수 있는가?

이 문제는 모든 부분수열을 탐색해야 하는 문제이므로, 완전 탐색(Brute Force)이 가능한지 먼저 확인해야 한다. N이 최대 20이므로, 각 원소를 선택하거나 선택하지 않는 모든 경우를 탐색하면 총 \(2^N\)개의 경우의 수가 발생한다. 최악의 경우 \(2^{20}\)  = 1,048,576개의 부분수열을 탐색해야 한다.

일반적으로 1초 안에 약 \(10^8\) 번의 연산이 가능하므로, 이 문제는 최대 2초의 제한 시간이므로 충분히 해결 가능하다.

결론적으로, 모든 부분수열을 탐색하는 완전 탐색 방식이 가능하다.

 

하지만 만약 N이 30 이상이었다면?

• \( O(2^{30}) \) = 약 10억 번의 연산이므로 시간 초과 발생 가능!
• 이 경우 Meet-in-the-Middle 기법을 활용할 수 있다. 이 방법은 수열을 두 개의 부분으로 나눈 후, 각각의 부분집합에서 가능한 모든 부분합을 구한 뒤, 이를 이분 탐색과 같은 기법으로 합쳐 빠르게 원하는 값을 찾는 방식이다. 이렇게 하면 시간 복잡도를 \( O(2^{N/2}) \)로 줄일 수 있어, 더 큰 입력도 효율적으로 처리할 수 있다.

어떤 방식으로 탐색할 것인가?

부분수열을 구하는 방법에는 여러 가지가 있다.

1. 비트마스크(bitmask)를 활용한 부분수열 생성
   • \(2^N\)개의 부분수열을 만들기 위해 이진수를 활용하여 각 원소의 포함 여부를 결정하는 방식이다.
   • N이 작을 때 효과적이지만, N이 커지면 메모리 사용량이 증가한다.
2. 재귀를 이용한 부분수열 생성
   • 특정 원소를 포함할지, 포함하지 않을지를 선택하는 방식으로 모든 부분수열을 탐색할 수 있다.
   • 이 과정은 트리 구조로 표현할 수 있으며, 한 경로를 끝까지 탐색한 후 다시 돌아오는 방식으로 진행되므로 깊이 우선 탐색(DFS) 방식으로 동작하며, 백트래킹을 적용하면 불필요한 탐색을 줄일 수 있다.
3. 동적 계획법(DP) 활용
   • 부분합을 저장하는 방식으로, 이전 계산 결과를 활용하여 새로운 결과를 만들어내는 방식이다.
   • 하지만, 이 문제는 모든 경우의 수를 다 고려해야 하므로 DP보다는 완전 탐색이 더 적절하다.

이 중 DFS(재귀 호출)를 활용한 방법이 직관적이고 간결하게 해결할 수 있는 방법이라고 판단했다.

 

DFS를 활용한 부분수열 탐색 과정

예를 들어, 수열이 [1,2,3][1, 2, 3][1,2,3]일 때, 첫 번째 원소 1을 포함할지 여부를 결정하면,

• 1을 포함하는 경우 → 다음 원소 2를 고려
• 1을 포함하지 않는 경우 → 다음 원소 2를 고려

이런 방식으로 각 원소에 대해 포함/미포함을 선택하는 과정이 이어지므로, 트리 구조로 표현할 수 있다.

탐색을 수행할 때,

1. 현재 선택한 원소들의 합을 누적하면서 다음 원소를 탐색한다.
2. 모든 원소에 대한 선택이 끝나면, 현재까지의 합이 S인지 확인한다.
3. 모든 원소를 탐색한 후에는, 이전 선택으로 돌아가(백트래킹) 다른 경우를 탐색한다. (이 경우, 현재까지 선택했던 원소를 되돌리고 다른 경우를 탐색한다.)
4. 이처럼 각 원소에 대해 하나의 선택(포함/미포함)을 확정한 상태에서 다음 원소를 탐색해야 하므로, 한 경로를 끝까지 탐색한 후 다시 돌아오는 방식이 된다.

즉, DFS 탐색을 수행하며, 각 단계에서 현재까지의 합을 유지하면서 다음 원소를 선택할지 결정하는 방식으로 진행된다.
이 과정은 다음과 같이 DFS 함수로 구현된다.

1. dfs(idx, current_sum) 함수에서 현재까지 선택한 원소들의 합을 유지한다.
2. 현재 부분수열의 합이 S와 같다면 count를 증가시킨다. (단, 공집합 제외)
3. 모든 원소를 탐색하면 종료한다.
4. 현재 인덱스 이후의 원소들에 대해 탐색을 진행한다 (중복 선택 방지).
5. 재귀적으로 다음 원소를 선택할지 말지를 결정한다.

---

구현

이 코드를 작성하면서 몇 가지 고민했던 부분이 있었다.

 

1️⃣ DFS의 시작을 -1로 설정한 이유

처음에는 dfs(0, numbers[0])과 같이 첫 번째 원소부터 시작하는 방식으로 구현하려고 했다. 하지만 이렇게 하면 첫 번째 원소를 반드시 포함해야 하는 문제가 생긴다.
DFS를 시작할 때, 처음에는 아무 원소도 선택하지 않은 상태(-1)에서 시작해야 한다. 이를 위해 dfs(-1, 0)을 호출하여, 첫 번째 원소를 포함할지 말지를 결정하는 출발점으로 사용한다. 이때, -1은 실제로 탐색하는 인덱스가 아니라, "아무 원소도 선택하지 않은 상태"를 나타내는 역할을 한다.

 

2️⃣ 부분수열을 어떻게 탐색할 것인가?

부분수열은 순서가 유지된 상태에서 원소를 선택해야 한다.
따라서, 현재 원소 이후의 원소들만 탐색하도록 for next_idx in range(idx + 1, N)을 사용하여 진행한다. 이렇게 하면 동일한 원소가 다시 선택되는 일이 없고, 올바른 부분수열을 만들 수 있다.

 

3️⃣ 공집합을 어떻게 처리할 것인가?

이 문제에서는 공집합(아무것도 선택하지 않은 경우)을 제외해야 한다.
이를 처리하는 방식에는 두 가지 방법이 있다.

 

🔹 (1) 공집합을 포함한 후 마지막에 제외하는 방법

• DFS 탐색을 할 때, 공집합도 포함하여 카운트한 후, 마지막에 공집합을 빼는 방식이다.
• current_sum == s일 때, 공집합을 포함한 모든 경우를 세고, 마지막에 cnt -= 1을 수행하여 공집합을 제거한다.

n, s = map(int, input().split())
arr = list(map(int, input().split()))

cnt = 0

def dfs(idx, current_sum):
    global cnt
    if current_sum == s:  
        cnt += 1  # 공집합 포함하여 카운트

    if idx == n - 1:
        return

    for next_idx in range(idx + 1, n):
        dfs(next_idx, current_sum + arr[next_idx])

dfs(-1, 0)  # 공집합 포함한 상태에서 시작
cnt -= 1  # 마지막에 공집합(아무것도 선택하지 않은 경우) 제거

print(cnt)

 

🔹 (2) 공집합을 애초에 세지 않는 방법 (자동 제외)

• DFS 탐색을 할 때, 공집합을 아예 카운트하지 않도록 조건을 추가하는 방식이다.
• if idx >= 0 and current_sum == s:를 사용하여, idx가 -1인 경우(공집합 상태)에는 카운트되지 않도록 한다.
• 이렇게 하면 공집합이 애초에 탐색 과정에서 배제되므로 cnt -= 1을 해줄 필요가 없다.

n, s = map(int, input().split())
arr = list(map(int, input().split()))

cnt = 0

def dfs(idx, current_sum):
    global cnt
    if idx >= 0 and current_sum == s: # 공집합 제외 조건 추가
        cnt += 1  # 부분수열의 합이 s가 되는 경우 카운트

    if idx == n - 1:
        return  # 모든 원소 탐색 완료

    for next_idx in range(idx + 1, n):
        dfs(next_idx, current_sum + arr[next_idx])

dfs(-1, 0)   # 공집합은 자동으로 제외됨

print(cnt)

---

TIL

프로그래밍에서 입력을 받을 때, 특히 알고리즘 문제를 풀 때 입력 형식을 정확히 이해하는 것이 중요하다. 입력 방식에는 크게 두 가지가 있다.

첫 번째는 한 줄에 여러 개의 정수가 입력되는 경우다. 이 경우 input().split()을 사용하여 한 번에 문자열로 입력받은 뒤, map(int, ...)을 사용하여 정수 리스트로 변환하면 된다. 예를 들어, 백준 문제에서 5 0 또는 -7 -3 -2 5 8과 같이 한 줄에 여러 개의 숫자가 들어오면 다음과 같이 처리한다.

n, s = map(int, input().split())  # 공백을 기준으로 분리하여 정수로 변환
arr = list(map(int, input().split()))  # 리스트 형태로 저장

 

이렇게 하면 arr에는 [-7, -3, -2, 5, 8]이 저장된다.

 

두 번째는 각 줄마다 하나의 정수를 입력받는 경우다. 이 경우 input()을 여러 번 호출하여 각각 리스트에 저장하는 방식이 적절하다. 예를 들어, 5개의 정수를 한 줄씩 입력받아 리스트로 저장하려면 다음과 같이 작성할 수 있다.

arr = [int(input()) for _ in range(N)]

 

이 방식은 반복문을 사용하여 N개의 숫자를 입력받을 때 유용하다. 다만, 한 줄에 여러 개의 정수가 들어오는 경우와 헷갈리지 않도록 주의해야 한다.