단어 수학

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	58135	26802	17364	44.381%

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분 수열 중에서
그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다.
(1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다.
주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분 수열의 개수를 출력한다.

예제 입력 1

5 0
-7 -3 -2 5 8

예제 출력 1

1

출처

• 문제를 만든 사람: author5
• 문제의 오타를 찾은 사람: eric00513, jh05013
• 데이터를 추가한 사람: rdd6584
• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

---

추가 예제

예제 입력 A

5 -3
-3 -2 -1 0 1

예제 출력 A

6

예제 입력 B

5 -2
-1 -1 -1 -1 -1

예제 출력 B

10

예제 입력 C

12 1000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 -1000000

예제 출력 C

66

예제 입력 D

8 22
10 8 -6 6 0 10 5 3

예제 출력 D

6

실패 코드 1

#include <iostream>
#include <queue>
#include <algorithm> 

using namespace std;

int N, S, result;
// N 정수의 개수  1<= N <=20 
// S 목표값  |S| <= 1,000,000
// result 목표값과 같아지는 부분수열의 개수

#define MAX 20
// 많이 사용할 것 같아 매크로로 뚫어 놓음

int numbers[MAX] = { 0 };
// 수열들 0으로 초기화

struct MyStruct
{
	int sumNumber;
	int sNumbers[MAX];
}temp, temp2;

queue<MyStruct> myQueue;

// 입력 값을 받는 함수
void SettingConditions()
{
	cin >> N >> S;

	for (int i = 0; i < N; i++)
	{
		cin >> numbers[i];
	}
}

void BFS()
{
	temp.sumNumber = 0;
	copy(numbers, numbers + MAX, temp.sNumbers);
	myQueue.push(temp);

	while (!myQueue.empty())
	{
		temp = myQueue.front();
		myQueue.pop();

		for (int i = 0; i < MAX; i++)
		{
			temp2 = temp;

			if (temp2.sNumbers[i] == 0)
			{
				continue;
			}

			int tempNumber = temp.sNumbers[i];
			temp2.sumNumber += temp.sNumbers[i];

			if (temp2.sumNumber == S)
			{
				result++;
			}
			temp2.sNumbers[i] = 0;
			myQueue.push(temp2);
		}
	}
}

int main()
{
	SettingConditions();
	BFS();

	cout << "결과 : " << result;
	return 0;
}

BFS로 접근

예제가

3 6
1 2 3 이라면

123 132
213 231
312 321

을 구분하지 못하는 난감한 상황이 발생하였다.

실패 코드 2

#include <iostream>
#include <queue>
#include <algorithm> 
#include <set>
#include <string>

using namespace std;

int N, S, result;
// N 정수의 개수  1<= N <=20 
// S 목표값  |S| <= 1,000,000
// result 목표값과 같아지는 부분수열의 개수

#define MAX 20
// 많이 사용할 것 같아 매크로로 뚫어 놓음

int numbers[MAX] = { 0 };
// 수열들 0으로 초기화

int resultarr[MAX];

struct MyStruct
{
	int sumNumber;
	int sNumbers[MAX];
	bool indexCheck[MAX] = {false};
	
}temp, temp2;

queue<MyStruct> myQueue;

// 입력 값을 받는 함수
void SettingConditions()
{
	cin >> N >> S;

	for (int i = 0; i < N; i++)
	{
		cin >> numbers[i];
	}
}

void Test()
{
	for (int i = 0; i < N; i++)
	{
		cout << numbers[i] << " ";
	}
	cout << "\n";
}

void DFS()
{
	Test();

	temp.sumNumber = 0;
	copy(numbers, numbers + N, temp.sNumbers);
	myQueue.push(temp);
	while (!myQueue.empty())
	{
		temp = myQueue.front();
		myQueue.pop();
		

		for (int i = 0; i < N; i++)
		{
			temp2 = temp;
			
			if (temp2.indexCheck[i] == true)
			{
				continue;
			}

			temp2.sumNumber += temp2.sNumbers[i];
			if (temp2.sumNumber == S)
			{
				result++;
				continue;
			}
			temp2.indexCheck[i] = true;
			myQueue.push(temp2);


		}



	}

}

int main()
{
	SettingConditions();
	DFS();

	cout << result;
	return 0;
}

Set을 통한 체크 및 방문 처리
메모리 부족 시간 초과로 터짐

DFS 로 변경

성공 코드 (DFS)

#include <iostream>

using namespace std;

int N, S, result;

// 자주 사용할 것 같아 매크로로 등록 
#define MAX 20

int numbers[MAX];

void SettingCondition()
{
	result = 0;

	cin >> N >> S;

	for (int i = 0; i < N; i++)
	{
		cin >> numbers[i];
	}
}

void DFS(int index, int total)
{
	if (index == N)
	{
		if (total == S)
		{
			result++;
			return;
		}
		//인덱스 마지막에 리턴
		return;
	}

	// 해당 인덱스의 원소를 사용할 때 / 안할 때
	DFS(index + 1, total + numbers[index]);
	DFS(index + 1, total);
}

int main()
{
	// 셋팅
	SettingCondition();
	DFS(0,0);
	
	// S = 0 이면 처음 시작 시 수열의 원소가 없지만 
	// total이 0 이므로 카운트가 하나 올라간다.
	if (S == 0) 
	{
		result--;
	}
	cout  << result;
	return 0;
}