[C++][백준 BOJ]1182_부분수열의 합.

문제 번호

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

1182번: 부분수열의 합

 

 

 

알고리즘 분류

 부르트포스, 백트래킹.

 

문제 풀이

 문제에서 주어진 수열의 모든 부분수열의 합을 구해보고 그중에서 조건에 맞는 답의 개수를 구하는 문제이다.

 

우선 몇개의 수로 이루어진 부분수열을 구할것인지 정해야한다.

// 몇개를 고를건지.
for (int i = 1; i <= N; i++)
{     
        ps(i, 0);
}

그리고 완전탐색을 이용하여 원하는 개수로 이루어진 부분수열을 temp라는 벡터에 저장하기로 하였다.

void ps(int cnt, int start)
{
    if (cnt == 0)
        return Check();

    for (int i = start; i < N; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            temp.push_back(arry[i]);
            ps(--cnt,i+1);
            cnt++;
            visited[i]=false;
            temp.pop_back();
        }
    }
}

부분수열을 완성하였다면 부분수열의 모든 수의 합이 문제에서 주어진 S와 같은지 확인한다.

void Check()
{
    int sum=0;
    for(int i=0; i<temp.size();i++)
        sum+=temp[i];

    if(sum==S)
        answer++;
}

 

전체 코드

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

#define MAX 20

vector<int> temp;
int N, S,answer=0;
int arry[MAX];
bool visited[MAX] = {false};

void Insert()
{
    for (int i = 0; i < N; i++)
        cin >> arry[i];
}

void Check()
{
    int sum=0;
    for(int i=0; i<temp.size();i++)
        sum+=temp[i];

    if(sum==S)
        answer++;
}

void ps(int cnt, int start)
{
    if (cnt == 0)
        return Check();

    for (int i = start; i < N; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            temp.push_back(arry[i]);
            ps(--cnt,i+1);
            cnt++;
            visited[i]=false;
            temp.pop_back();
        }
    }
}

int main()
{
    cin >> N >> S;
    Insert();

    // 몇개를 고를건지.
    for (int i = 1; i <= N; i++)
    {     
        ps(i, 0);
    }

    cout << answer;

    return 0;
}

특이사항

 특별하게 어려운부분은 없는 완전탐색 문제였다. 

비트를 이용하여 모든 부분수열을 구하는 방법도 있으니 연습하여 적용해 보아야겠다.