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

1182번: 부분수열의 합 (acmicpc.net)

1182번: 부분수열의 합

DFS 백트래킹을 사용해야했던 문제

DFS를 살펴보자..

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog (gmlwjd9405.github.io)

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

 

[백준/BOJ] 1182번 부분수열의 합 (C++) :: 노력의 천재 (tistory.com)

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

 

이 포스팅 참고해서 풀었는데

dfs를 사용하고,  sum 변수는 누적합을 나타냄

dfs로 깊이 탐색을 하면서 누적합에 다음 노드인 v[index]를 더한게 s와 같으면 count++ 해줌.

같지 않다면,

dfs(index+1, sum+v[index])를 호출해서 누적합을 갱신시키고 다음 벡터로 dfs를 재귀적으로 호출시키고,

dfs(index+1, sum)을 호출해서 다음 노드에 대해서 dfs를 호출시킨다.

 

최종 코드는 이러함

#include <vector>
#include <iostream>

using namespace std;

int n, s, m;
int count = 0;
vector<int> v;
    
void dfs(int index, int sum){
    if(index == n) return;
    if(sum+v[index] == s) count++;
    
    dfs(index+1, sum+v[index]);
    dfs(index+1, sum);
}

int main()
{
    cin >> n >> s;
    
    for(int i=0; i<n; i++){
        cin >> m;
        v.push_back(m);
    }
    
    dfs(0,0);
    cout << count;
    
    return 0;
}

 

코드가 간결하고 너무 좋은데, 내가 다음에 다시 풀려고 하면 이렇게 못 풀 것 같다

회의때 다른 방법에 대해서 얘기해볼 것

그리고 다음 dfs에 대해 공부할 때 다시 풀어보는 게 좋을 것 같다