[BOJ] 부분수열의 합

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

Level : S2

유형 : 부르트포스, 백트래킹

---

📌 문제 탐색하기

N (1<= N <= 20) : 정수의 갯수

S ( |S| <= 1,000,000): 부분 수열에 있는 원소들의 합

 

이 문제는 주어진 수열에서 내가 원소를 뽑아 부분수열을 만들 수 있다.

이때, 내가 뽑는 원소의 갯수는 정해지지 않았다. 즉 합이 S가 되기 위해 뽑을 수 있는 모든 경우의 수를 고려해야 한다.

 

조합을 생각해서 시간 복잡도를 대략 계산해볼 수 있다.

N의 최대가 20이므로 위의 조합에 대입해보면, 시간복잡도는 O(2^n)이다.

2^n이 최악의 시간복잡도이지만, 수의 최댓값이 20으로 약 1,000,000 + a 정도 밖에 되지 않는다.

 

따라서 '완전탐색'을 이용하여 뽑을 수 있는 원소의 갯수를 다 고려해본다.

 

📌  코드 설계하기

1. 정수의 갯수가 최대 20개이므로 배열의 크기가 21정도인 arr을 만들어 입력을 받는다.

2. S의 최대값이 1,000,000이므로 원소의 값을 더해갈 변수 sum을 987654321로 초기화 한다. (0으로 초기화 하면 안됨!)

3. 반복문을 이용하여 합에 넣을 첫번째 원소를 선택하고 sum을 선택한 원소값으로 설정한다.

4. select(idx) 메서드를 재귀적으로 호출하여 뽑을 수 있는 모든 경우의 수를 고려하며 원소의 합이 S가 되는지 따져본다.

 

- select의 로직은 다음과 같다.

*지금까지 더한 원소의 합 sum이 s와 같아지면 결과값인 ret을 증가시킨다.

*기저사례 : 매개변수 idx가 정수의 갯수인 n -1이 되었을 경우 함수를 종료한다.

*반복문을 idx+1부터 시작하여 수열의 원소를 택하고 sum에 더한다.

*이후 select를 재귀적으로 호출해 이 과정을 반복한다.

 

 

 

📌  시도 회차 수정 사항

[1회차]

if(sum == s){
        ret++;
        //print();
        //return; //0이 더해질 수도 있으니까 리턴하면 안됨
}

select 함수 내에 있는 위 조건문에서 return 코드를 추가한 것이 문제였다.

무엇이 문제냐면, 

입력:

3 -5

-5 0 5

 

위의 입력을 입력했을 때, 원소의 합 -5를 만족하는 경우의 수는 -5, (-5, 0) 2가지이므로 출력값이 2가 나와야 한다. 

하지만 위의 코드에 return을 추가한다면 -5 즉, 원소의 합(sum)이 s를 만족하는 순간 함수를 종료하여 (-5,0)과 같은 추가로 생길 수 있는 case를 고려하지 못한다. 

현재 충족되는 값, 즉 형태에서 어떤 원소가 더해지고 빼지는 순간 s를 무조건 위배할 것이라고 생각해서 'return을 통해 함수를 종료해야지' 라는 생각을 했다.

하지만 5, 0 또는 5, -1, 1 이런식으로 충족되는 값 이후 숫자들이 추가가 되도 s값을 충족할 수 있다.

이 부분을 고려하지 못했다.

 

[2회차]

print() 메소드를 만들어서 뽑히는 경우의 수를 전부 출력하면서 확인해봤다. 

따라서 오류를 해결할 수 있었다.

 

📌 정답 코드

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

int n, s, sum=987654321, ret=0;
vector<int> v;
int arr[21];

/*void print(){
    for(int i : v){
        cout << i << " ";
    }
    cout << "\n";
}*/

void select(int idx){
    if(sum == s){
        ret++;
        //print();
        //return; //0이 더해질 수도 있으니까 리턴하면 안됨
    }
    if(idx == n-1) return;

    for(int i= idx+1; i<n; i++){
        sum += arr[i];
        //v.push_back(arr[i]);
        select(i);

        //끝나면
        sum-=arr[i];
        //v.pop_back();
    }
}

int main(){

    cin >> n >> s;

    for(int i=0; i<n; i++){
        cin >> arr[i];
    }

    for(int i=0; i<n; i++){
        sum = arr[i];
        //v.push_back(arr[i]);
        select(i);
        //v.pop_back();
        
    }

    cout << ret << "\n";

    return 0;
}

 

📌 주석 지운 코드

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

int n, s, sum=987654321, ret=0;
vector<int> v;
int arr[21];

void select(int idx){
    if(sum == s){
        ret++;
    }
    if(idx == n-1) return;

    for(int i= idx+1; i<n; i++){
        sum += arr[i];
        select(i);

        //끝나면
        sum-=arr[i];
    }
}

int main(){

    cin >> n >> s;

    for(int i=0; i<n; i++){
        cin >> arr[i];
    }

    for(int i=0; i<n; i++){
        sum = arr[i];
        select(i);  
    }

    cout << ret << "\n";

    return 0;
}