BOJ_1182 / C++

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

1182번: 부분수열의 합

백준 1182번 문제입니다.

DFS와 재귀, 백트래킹을 이용해서 문제를 풀었습니다.

#include<iostream>
#define MAX 1000000
using namespace std;

int n,s,sum,cnt;
int arr[MAX];

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

void DFS(int i, int sum)
{
	if (i == n)
		return;
	if (sum + arr[i] == s) 
		cnt++;

	DFS(i + 1, sum);
	DFS(i + 1, sum + arr[i]);
}
void soution()
{
	DFS(0, 0);
}

int main(void)
{
	Input();
	soution();

	cout << cnt;
	return 0;
}

아이디어

우선 문제와 같은 케이스에서 N = 5일때 원소의 갯수가 1, 2, 3, 4, 5 일때 대한 모든 케이스를 DP를 이용해서 확인 하는 방향으로 고민을 했었는데, 생각을 정리를 하다보니 재귀를 활용하는것이 적합하다고 판단했고, 재귀를 이용한 탐색을 하려면 DFS를 활용 할 수 있다고 생각했다.

그런데 결정적으로 재귀를 이용할때 DFS(i +1, sum) , DFS(i+1 , sum + arr[i]) 처럼 i원소를 더했을때와 더하지 않았을때를 표현하는 방법에 익숙하지 않아서 다른 블로그들을 참고하게 되었다. 

고민을 하루 넘게 한것 같은데 생각을 코드로 표현하는 방법이 익숙치 않아서 도움을 받으니 간장계란밥을 계란없이 먹은것 같은 느낌이다. 더 노력하자