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

문제: 1182번: 부분수열의 합

basic-algo-lecture/workbook/0x0C.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x0C.md at master · encrypted-def/basic-algo-lecture

 

• 틀린 코드..

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;

int n, s;
int nums[20];
int visits1[1000001]; // 음수 방문 표시(절댓값)
int visits2[1000001]; // 양수 방문 표시
int sum = 0; // 재귀 돌면서 값을 뺐다 더했다..
int cnt = 0;

void Funct(int functN) {
	// 부분 수열의 합이 s 와 같으면 cnt 값 +1 하기(그리고 공집합이 아니어야 함)
	if (sum == s && functN != 0) {
		cnt++;
		return;
	}

	// 현재 부분수열의 크기가 5인데 위 조건문에 걸러지지 않았다면 그냥 빠져나가기..
	if (functN == n) {
		return;
	}

	// nums 를 돌면서 하나씩 더해줄것..
	for (int i = 0; i < n; i++) {
		// 방문 표시 확인(이미 방문했으면 그냥 지나가가ㅣ..)
		if (nums[i] < 0) {
			if (visits1[-nums[i]] == 1) {
				continue; 
			}
		}
		else {
			if (visits2[nums[i]] == 1) { 
				continue; 
			}
		}

		// 방문..
		if (nums[i] < 0) {
			visits1[-nums[i]] = 1; // 방문 표시
			sum += nums[i];

			Funct(functN + 1); // 재귀 돌리기

			visits1[-nums[i]] = 0; // 방문 표시 없애기
			sum -= nums[i];
		}
		else if (nums[i] > 0) {
			visits2[nums[i]] = 1; // 방문 표시
			sum += nums[i];

			Funct(functN + 1); // 재귀 돌리기

			visits2[nums[i]] = 0; // 방문 표시 지우기
			sum -= nums[i];
		}
		else {
			// 0 방문 표시
			visits1[0] = 1;
			visits2[0] = 1;

			Funct(functN + 1); // 재귀 돌리기

			// 0 방문 표시 지우기..
			visits1[0] = 0;
			visits2[0] = 0;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		nums[i] = tmp;
	}
	Funct(0); // 일단 0으로 시작..
	cout << cnt;

	return 0;
}

 

이 풀이의 문제점은 중복된 수열까지 cnt 에 더해버리는 것..

 

 

• 정답 코드

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;

int n, s;
int nums[21];
int cnt = 0;

void Funct(int functN, int tmpSum) {
	if (functN == n) {
		if (tmpSum == s) {
			cnt++;
		}
		return;
	}

	// 재귀 호출할 때 현재 sum 값에 현재 값을 더한 경우와 안 더한 경우로 나눠서..
	Funct(functN + 1, tmpSum); // 안 더한 경우
	Funct(functN + 1, tmpSum + nums[functN]); // 더한 경우
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

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

	Funct(0, 0);

	if (s == 0)
		cnt--; // 공집합인 경우 빼야함..
	cout << cnt;

	return 0;
}

 

결국 강의 영상 보고 풀었는데 훨씬 쉽게 푸는 방법이 있었다..

 

다음 단계로 넘어가려고 할 때 현재 값을 더하는 경우와 안 더하는 경우 두 가지로 나눠서 재귀적으로 호출하면 되는 거였다;; 그러다가 현재 functN 값이 n 과 같아지면 sum 이 s 와 같은지 확인하고 같으면 cnt++ 해주면 되는 거였다..

 

더하는 경우와 안 더하는 경우로 나누는 방식을 앞으로도 기억하고 있어야 할 것 같다;;;

 

 

 

참고자료:

BaaaaaaaarkingDog | [실전 알고리즘] 0x0C강 - 백트래킹

[실전 알고리즘] 0x0C강 - 백트래킹