백준 1182번: 부분수열의 합

[문제 링크]

1182번: 부분수열의 합

---

부분수열의 정의를 제대로 알고, 문제를 정확히 이해하면 쉽게 풀리는 문제라고 생각한다.

1~N개의 수를 포함하는 모든 조합들 중 순서만 다른 조합을 제외한 나머지 조합들을 대상으로 조합이 가진 원소들의 합이 입력된 값과 같다면 카운트를 1증가시키고 마지막으로 결과를 출력하면 원하는 답을 얻을 수 있다.

---

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> sequence;
int numCnt, stand, cnt=0;
void Solution(int start, int sum)
{
    for (int i = start; i < numCnt; i++)
        Solution(i + 1, sum+sequence[i]);
 
    if (start == 0 && sum == stand) return;    // stand가 0일 때 의도치않은 cnt값 증가 방지
    if (sum == stand) cnt++;
}
int main(void)
{
    cin >> numCnt >> stand;
    for (int i = 0; i < numCnt; i++)
    {
        int n;
        cin >> n;
        sequence.push_back(n);
    }
    Solution(0,0);
    cout << cnt << endl;
    return 0;
}

 

알고리즘 200일 프로젝트 - 8day

내일도 열심히!