[DFS] 14225 부분수열의 합

14225번 부분수열의 합

 

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

 

문제

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.

예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.

 

입력

첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20)

둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

 

예제 입력

3
5 1 2

3
2 1 4

4
2 1 2 7

 

예제 출력

4

8

6

 

해결방법

백트래킹을 통해 모든 경우를 DFS 탐색 해보는 문제이다

n≦20 이기 때문에 O(2^20) 으로 시간 초과가 발생하지 않는다

 

1 2 3 의 집합에 대해 탐색을 한다고 가정해보자

각각 원소가 포함되거나 포함되지 않는 2가지의 경우로 나뉜다

이런식으로 DFS 탐색을 하며 모든 정점을 방문하는 것이다

시간복잡도는 O(2^n) 이 될 것이다

 

이를 코드로 나타내면 이러하다

void dfs(int ind,int sum){
    // 노드의 끝까지 간 경우
    if(ind == n){
        num[sum] = true;
        return;
    }
    
    // ind 인덱스 노드를 포함하는 경우
    dfs(ind+1,sum+arr[ind]);
    // ind 인덱스 노드를 포함하지 않는 경우
    dfs(ind+1,sum);
}

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 21
#define MAX_SUM 2000001
#define INF 987654321
using namespace std;

int n;
int arr[MAX];
bool num[MAX_SUM];

void dfs(int ind,int sum){
    // 노드의 끝까지 간 경우
    if(ind == n){
        num[sum] = true;
        return;
    }
    
    // ind 인덱스 노드를 포함하는 경우
    dfs(ind+1,sum+arr[ind]);
    // ind 인덱스 노드를 포함하지 않는 경우
    dfs(ind+1,sum);
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    
    memset(num, false, sizeof(num));
    
    dfs(0,0);
    
    for(int i=1; i<MAX_SUM; i++){
        if(!num[i]){
            cout << i << "\n";
            break;
        }
    }
}