알고리즘
[C++] Boj 1182 부분수열의 합
(ꐦ •᷄ࡇ•᷅)
2025. 1. 17. 11:25
문제 링크
접근
모든 경우의 수를 확인하는 백트래킹 문제이다. N개의 정수로 이루어진 수열이 있을 때, 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성해야 한다.
이때, 중요한 점은 크기가 양수인 부분 수열 중에서 경우의 수를 구해야 한다는 것이다. 이 말은, 공집합은 포함하지 않는다는 말이다.
이 문제는 중학교 때 배웠던 부분 집합 구하기 경우의 수 문제를 떠올려 쉽게 해결할 수 있다.
만약 n1, n2, n3의 수 중 부분 수열을 만들어 합 S를 만들어야 한다면, n1을 선택하고, 안 하고, n2를 선택하고, 안 하고를 반복해서 선택한 숫자들의 합이 S가 되게 만들면 된다.
이때 주의해야 할 점은 S가 1 이상인 경우는 상관없으나 S가 0일 때 아무것도 선택하지 않을 수 있다. 그것이 바로 공집합이고, 따라서 마지막에 예외 처리를 해 주어야 한다.
코드
#include<iostream>
#include <vector>
using namespace std;
int N, S;
int cnt;
// 접근
// 숫자들 중에 특정 수를 더할 것인지, 안 더할 것인지 여부를 판단하여 진행한다.
// int: 정수
// bool: 그 정수를 방문 했는지
vector<pair<int, bool>> numbers;
// numberConut: 몇 번째 숫자까지 순회했는지
// numbersSum: 현재 고른 수 들의 합
void Solve(int numberConut, int numbersSum)
{
if (N == numberConut)
{
if (S == numbersSum) cnt++;
return;
}
Solve(numberConut + 1, numbersSum + numbers[numberConut].first);
Solve(numberConut + 1, numbersSum);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> S;
for (int i = 0; i < N; i++)
{
int tmp;
cin >> tmp;
numbers.push_back({ tmp, false });
}
Solve(0, 0);
// 합이 0일 때 아무것도 선택하지 않을 수 있으므로 그걸 제외시킨다.
if (S == 0) cnt--;
cout << cnt;
return 0;
}