https://www.acmicpc.net/problem/1182
문제
> N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.접근
부분수열이 뭔지 검색해봤다. 예를 들어 수열이 1,3,5가 있다면 1,3, 1,5 3,5 1,3,5가 있지만 3,1 5,3 등 반대로는 안되는 수열로 이해했다.
그럼 반복문으로 각 자리에 올 수를 잡아 놓고 재귀로 다음 자리에 올 수를 고르며 1,3, 1,5 3,5 1,3,5처럼 가능한 모든 경우를 따져주게 재귀를 짜면된다.
그래서 처음 반복문을 i는 0부터 N까지로 하고 0인 sum에 각각의 i인덱스에 해당하는 값을 더해 S와 같은지 비교하고 cnt누적을 결정한다. 그리고 for문이 끝나기 전 재귀로 i+1과 방금 계산한 sum을 다음으로 넘겨준다.
그럼 첫 재귀에선 총 3가지 분기 1과 3과 5가 나오고 다음 재귀에선 1에선 1,3과 1,5두 분기가 나온다. 1,3은 1,3,5로 갈 수 있고 1,5는 i과 N이 같아 반복문이 끝나 재귀가 끝난다.
1분기 이후 3에선 3,5만 가능하고 5에선 더 갈 수 없다. 이렇게 모든 경우를 다 따져줄 수 있다.
문제해결
> 수열의 수, 목표하는 S를 입력받고 수열을 담을 벡터와 부분수열의 개수 cnt를 선언해주고 이를 찾는 Seq 메소드를 정의해준다.
> 인자로 인덱스와 sum을 받아준다. sum은 수열들의 합을 계산해 S와 비교하는데 쓰인다.
> 만약 인덱스가 N보다 크거나같다면 반복문을 할 수 없으므로 재귀를 깨주도록 해주고 재귀부분을 구현한다.
> 인자로 받은 인덱스를 시작으로 반복문을 N까지 하며 sum으로 받은 수열의 누적된 합을 tmp로 복사해와 인덱스에 해당하는 num수열의 값을 더한다.
S와 같다면 부분수열이므로 cnt를 누적하고 아니면 다음 수열을 탐색하기위해 재귀로 i+1, 방금까지 쌓인 수열의 합tmp를 넘긴다.
> main함수에선 N, S와 수열을 입력받고 Seq메소드에 0,0을 넣어 호출해준다. 끝나면 cnt를 출력해준다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, S;
vector<int> num;
int cnt = 0;
void Seq(int index, int sum)
{
if (index >= N) return;
for (int i = index; i < N; i++)
{
int tmp = sum + num[i];
if (tmp == S) cnt++;
Seq(i + 1, tmp);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> S;
num.resize(N);
for (int i = 0; i < N; i++) cin >> num[i];
Seq(0, 0);
cout << cnt << '\n';
}
후기
처음에 sum에 num(i)를 추가하는 부분에서 i가 아닌 index를 넣었었다. 무한루프가 발생해 보니 여기가 문제였다. 반복문을 통해 각각 다른 i에 대한 num값을 넣어야하는데 해당 재귀의 인자로 온 index만 계속넣어주니 그랬다.
이를 수정하니 잘 나와 제출했는데 틀렸다.
다시 처음부터 따라가며 보니 sum을 for문 안에서 sum+=num(i)로 수정을 해버리면 다음 반복문에서 이 변질된 sum으로 계산을 해버리니 입력예제는 운좋게 맞았지만 다른 예제에선 틀리는것이다. 그래서 현 재귀에 있는 반복문들이 오염되지 않은 sum을 쓰도록 sum을 tmp로 복사해주고 tmp로 처리를 해주었다.
