[BOJ] #1182 부분수열의 합
https://www.acmicpc.net/problem/1182
1182번: 부분수열의 합
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
https://terms.naver.com/entry.nhn?docId=5668858&cid=60207&categoryId=60207
부분수열
어떤 무한 수열의 부분수열은 원래 수열에서 항의 일부를 골라 항의 번호가 작은 것부터 나열하여 얻은 무한 수열이다. [목차] 1.정의 1.1.보기 1 1.2.보기 2 2.부분수열과 수렴성 3.부분수열과 상극한 4.같이 읽기 [ 정의 ] 어떤 수열 (a_n) 이 있을 때, 단조증가함수 f: \mathbb{N}\to \mathbb{N}에 대하여 (a_{f(n)}) 을 수열 (a_n)의 부분수열(subsequence)이라고 한다. 보기 1 (a_n)=(1^2,
terms.naver.com
부분수열이 무엇인 지 알아야 풀 수 있는 문제이다.
수열에서 항의 일부를 골라 순서대로 나열한 수열을 부분 수열이라고 한다.
이 때 고르는 수열은 일정한 법칙 없이 뽑아도 된다. 순서만 맞으면...
<풀이 과정>
1. 각각의 수를 더하고 지나갈 때와 더하지 않고 지나갈 때를 고려하여 부분수열의 모든 경우의 수를 체크한다.
(-> 이부분은 재귀호출로 해결한다.)
2. 매 호출 마다 부분수열의 합이 S인지, 마지막 인덱스까지 확인했는지 검사한다.
3. S 값이 0일 때를 고려하여 모든 값을 더하지 않고 뛰어넘은 경우를 제거해준다.
어려워서 여기저기 찾아보며 했는데, 처음 이해하기까지가 힘들었다.
#include <iostream>
#include <vector>
using namespace std;
int answer = 0;
int N, S;
int arr[10000] = { 0 };
void sumSubseq(int i, int sum) {
// 부분수열의 합이 S이고 마지막까지 확인을 했을 때 answer += 1
if (sum == S && i == N) {
answer += 1;
return;
}
// 부분수열의 합이 S가 아니지만 마지막까지 확인을 했을 때 return
if (i == N)
return;
// 현재 확인한 값을 더할 때
sumSubseq(i + 1, sum + arr[i]);
// 현재 확인한 값을 더하지 않을 때
sumSubseq(i + 1, sum);
}
int main()
{
cin >> N >> S;
for (int i = 0; i < N; i++)
cin >> arr[i];
sumSubseq(0, 0);
// S가 0일 때 모든 값을 더하지 않고 뛰어넘은 경우를 제거
if (S == 0)
answer--;
cout << answer << endl;
}
<결과>
