[DFS] 백준 1182번 부분 수열의 합(C++)

 

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

 

 

정말 많이 풀어본 유형 및 예제군...

수열문제라...

 

 

[DFS] 백준 15649번 N과 M (1,2,3) (C++)

[DFS] 백준 15649번 N과 M (1,2,3) (C++)

n과 m 시리즈를 한번보고 와야겠군?

정말 단순히

 

그냥!

 

들어오는 대로 더해주고 

0인지 확인하고

반복하면된다

 

단 주의해야 할 점은

모든 수열이 아닌, 한가지 경우 만이므로

(예를들어 1 3 5 의 경우 수열이 135 153 315 351 531 513 6개의 경우가 존재하지만, 1 3 5 하나만 치겠다는 뜻)

idx를 잘 설정해 주어야 한다.

 

이전 인덱스 값이 나오지 않도록 해야하는데 그것은 코드에서 보여주겠다

 

#include <iostream>

#include <cmath>

#include <vector>

using namespace std;

vector<long long> v;

int n, tsum, sum = 0, idx;

bool visited[20];

long long arr[20];

int count = 0;

void task(int depth, int idx);

int main()

{

    cin >> n >> tsum;

    for (int i = 0; i < n; i++)

    {

        cin >> arr[i];

    }

    task(0, 0);

    cout << count << "\n";

}

void task(int depth, int idx)

{

    if (!v.empty() && sum == tsum)

        count++;

    for (int i = idx; i < n; i++)

    {

        if (!visited[i])

        {

            visited[i] = true;

            sum += arr[i];

            v.push_back(arr[i]);

            task(depth + 1, i + 1);

            sum -= arr[i];

            v.pop_back();

            visited[i] = false;

        }

    }

}

짜잔

매개변수 idx를 추가하고 , dfs 백트래킹 함수에서 i+1을 전달함으로써, 이전 인덱스의 값은 찾지 않는다.

 

그리고 벡터를 왜 썻냐고 물을수도 있는데 그 이유는 sum==tsum일때, tsum이 처음에 0으로 되는 경우, 바로 조건문을 통과할 수 있기 때문에.. empty가 아닌 경우만 통과하도록 써줌