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

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

 

N개의 정수의 수열을 입력으로 받고, 그 수열의 크기가 양수인(크기가 1개 이상인) 부분 수열 중 합이 S가 되는 경우의 수를 구하는 문제입니다.

 

처음에 접근했던 방식으로는, 백트래킹으로 원래 수열을 맨 처음부터 살펴보며 부분 수열을 만듭니다. 원소 개수가 1개 이상인 부분 수열이 만들어지면 합을 구하고 그 합이 S와 같아지면 cnt를 1 증가시킵니다.

 

백트래킹을 사용하여 func(nx,x) 함수를 만듭니다. 여기서 nx는 현재 만들고 있는 부분 수열의 원소 개수, x는 현재 추가해야 할 수의 원래 수열에서의 순서입니다. 

부분 수열을 구하면서 수열의 크기가 양수일 때 합이 S와 같으면 cnt를 증가시킵니다.

if (isused[i] || x>i) continue; 와 같은 조건을 추가하여 부분 수열의 중복을 피합니다.

 

#include<iostream>
using namespace std;

int n, s;
int cnt;
bool isused[22];
int arr[22];
int sum;

void func(int nx,int x)
{
	//if (nx == n) return;	//isused로 점점 고려할 수열의 원소 수가 줄어들기 때문에 이 조건에는 어차피 한번밖에 걸리지 않는다 

	if (sum == s && nx != 0)		
	{
		cnt++;
		//return;	//return 하면 sum과 s 같아졌을때 그 이후 수열을 더하지 않고 return 해버린다
	}

	for (int i = 0 ; i < n; i++)
	{
		
		if (isused[i] || x>i) continue;		// 이미 합을 구했던 부분수열은 고려하지 않음

		isused[i] = true;
		sum += arr[i];
		func(nx + 1,i);

		isused[i] = false;
		sum -= arr[i];
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> s;
	for (int i = 0 ; i < n; i++)
		cin >> arr[i];

	func(0,0);

	cout << cnt;

	return 0;
}

 

예제 입력으로 만들어지는 부분 수열은 다음과 같습니다.

 

 

이러한 방법을 사용해서도 정답은 받을 수 있지만.. 사실 포스팅을 작성하면서 부분 수열이 만들어지는 부분이 어떻게 동작하는지 눈에 들어오지 않고 이해가 어렵다는 것을 깨달았습니다. (사실 포스팅하는 시점에서 몇 달 전에 풀었던 문제인데 if (isused[i] || x>i) continue; 와 같은 코드가 어떻게 동작하는지 한 번에 보이지 않아 출력을 다시 해보아야 했습니다.)

 

 

그래서 다른 방법으로 접근합니다. 원래의 수열의 맨 앞에서부터 각 수를 더할지 말지를 고려합니다. 다시 말해 모든 부분 수열의 합 상태 공간 트리를 그린다고 생각합니다.

func함수를 func(cur, tot)으로 다시 작성하고, 여기서 cur은 더할지 말지 결정할 수의 순번, tot은 현재 수열의 총합을 의미합니다. 

 

예제 입력을 가지고 위에서 언급한 모든 부분 수열의 합 상태 공간 트리를 그림으로 그린다면 다음과 같습니다.

수열의 수를 맨 처음부터 보면서 현재 총합에 더할지 말지 결정하며 그려나갑니다

 

#include<iostream>
using namespace std;

int n, s;
int arr[22];
int cnt;

void func(int cur, int tot)
{
	if (cur == n)
	{
		if (tot == s)	// 각 수가 들어가는지 안들어가는지 모든 경우의 수(cur==n)를 구하는 것이므로
						// 합이 s면 return;
		{
			cnt++;
		}
		return;
	}
	func(cur + 1, tot);
	func(cur + 1, tot + arr[cur]);
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	func(0, 0);

	if (s == 0) cnt--;	//s가 0일때는 공집합 일때를 고려(-1)
	cout << cnt;

	return 0;
}

 

위의 코드보다 동작을 한눈에 이해하기 쉽습니다. 재귀를 사용해 현재 보고 있는 수(arr[cur])를 더하는 경우와 더하지 않는 경우만 고려하면 됩니다.

 

다만 S가 0일 때는 수열의 원소 개수가 양수이어야 하기 때문에 공집합인 경우를 빼주어야 합니다.