백준 1182번: 부분수열의 합

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

1182번: 부분수열의 합

 

할 수 있는 모든 경우의 수를 모두 다 따져서(백트래킹) 합이 S와 일치하는 경우 개수를 세어주면 됩니다.

처음에는 전형적인 백트래킹으로 코드를 짰지만, 다른 분의 코드를 보니까 부분집합 생성으로 푸시더라고요. 그래서 두가지 방법으로 모두 다 풀어봤습니다.

 

1. 전형적인 백트래킹

#include <iostream>
#include <vector>
using namespace std;

int N, S;
int arr[21];
vector<int> pickedIndex;
int cnt = 0;

// n은 이미 뽑은 원소의 개수. k는 총 뽑을 원소의 개수.
void solve(int& sum, int n, int k) {
    if(n == k) {
        if(sum == S) cnt++;
        return;
    }
    int nxt;
    // 뽑은 원소가 없으면 index를 0으로 만들어 준다.
    if(pickedIndex.empty()) nxt = 0;
    // 중복 방지. 이번에 뽑을 것은 이미 뽑은 거 바로 다음 인덱스를 선택함.
    else nxt = pickedIndex.back() + 1;
    // 맨 마지막 원소가 이미 뽑혔을 경우에는 반복문을 돌지 않음.
    for(int i = nxt; i < N; i++) {
        // 원소 선택.
        pickedIndex.push_back(i);
        sum += arr[i];
        solve(sum, n+1, k);
        pickedIndex.pop_back();
        sum -= arr[i];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> S;
    for(int i = 0; i < N; i++) cin >> arr[i];
    for(int i = 1; i <= N; i++) {
        int sum = 0;
        solve(sum, 0, i);
    }
    cout << cnt;
    return 0;
}

 

2. 부분집합 풀이

바킹독님 강의를 보면서 상태공간트리라는 것을 배웠는데요. 이를 이용해서 부분집합을 한번 생성하는 것을 먼저 설명하겠습니다.

예시로 집합 U = {1, 2, 3} 일 때 부분집합을 들어보겠습니다.

부분집합 생성을 나타낸 상태공간트리

 

분기가 나눠질 때 왼쪽으로 갈 때는 원소를 선택하지 않고, 오른쪽으로 갈 때는 원소를 선택합니다. 깊이가 가장 깊은 곳에 있는 집합들이 바로 부분집합입니다. 재귀를 이용한 부분집합 생성. 이를 이용해서 이문제를 정말 간결하게 풀어낼 수 있어요.

 

#include <iostream>
using namespace std;

int N, S;
int arr[20];
int dfs(int i, int sum) {
    if(i == N) return sum == S;
    return dfs(i+1, sum) + dfs(i+1, sum+arr[i]);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> S;
    for(int i = 0; i < N; i++) cin >> arr[i];
    cout << dfs(0, 0) - !S;
    return 0;
}

 

차이점은 분기마다 배열에 원소를 저장하는 것이 아니라 합을 저장하고 있습니다. 재귀하는 부분을 보면 2가지 분기를 선택하는 것을 볼 수 있습니다. 출력할 때 !S를 빼주는 것은 S가 0이라면 공집합인 경우를 1번 카운트 하게 되는데, 공집합은 세면 안되기 때문에 빼줍니다. S가 0이 아니면 !S는 항상 0입니다.

 

!S 빼주는 건 문제 풀고 다른 사람들 풀이 보면서 배웠어요. 2명 ~ 3명 정도의 코드를 보는 편인데, 주로 짧은 코드를 봐요. 그러면 항상 1가지라도 배워가는 듯 합니다.