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

#include <iostream>

#define MAX 22
using namespace std;

int N, S;
int arr[MAX];

int result = 0;
void Solve(const int & total, const int & length, int level)
{
	if (1 <= level && total == S)
	{
		++result;
	}

	for (int i = length + 1; i < N; ++i)
	{
		Solve(total + arr[i], i, level + 1);
	}
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> S;

	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i];
		if (arr[i] == S) ++result;
	}
	Solve(0, -1, -1);
	cout << result;
	return 0;
}

---

||사고 과정

처음엔 수열이 N개라면 N^4로 루프를 돌리면서 S에 맞는 값이면 카운트해서 풀이하려고 했다.

근데 쓸모없는 삽질을 통해 중복된 수열이 안된다는 것을 깨달았다..

 

그래도 이전 문제에서 시간을 줄이려고 하면서 이런 중복된걸 제외하는 코드가 생각나서 좀 쉽게 다가갈 수 있었다.

//중복포함
for(int i = 0; i < N; ++i)
{
	for(int j = 0; j < N; ++j)
	{
		cout << arr[i][j];
	}	
}

//중복제거
for(int i = 0; i < N; ++i)
{
	for(int j = i; j < N; ++j)
	{
		cout << arr[i][j];
	}	
}

이런 느낌인데 이걸 이번 문제에 대입하면

각 숫자는 수열의 번호

이렇게 볼 수 있다.

각 부모의 숫자보다 이하인 경우는 없다.

 

이를 이용하여 반복문을 돌려주었고 해결했다.

---

||사용 기법

• Back tracking

---

||풀면서 느낀 것

• 문제이해하기

문제만 계속 풀다보니까 집중력이 떨어져서 문제 파악을 잘 못했다.

생각해야할 예외도 많았는데 이 때문에 정말 많은 시간을 소모했다.

• 매개변수의 정확한 의미

length와 level을 두루뭉실하게 잡아놔서 헷갈리는 바람에 시간을 많이 소모함..

항상 단단한 설계가 시간을 아껴준다는걸 느낀다..

---

||더 나은 풀이

#include <stdio.h>

int a[20];

int n,m;
int cnt =0;

void f(int idx,int sum){
	if(sum==m) cnt++;
	for(int i=idx+1;i<n;i++) f(i,sum+a[i]);
}

int main(void){
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	for(int i=0;i<n;i++) f(i,a[i]);
	printf("%d",cnt);
}

다른 분의 풀이인데 같은 방식이나 내 코드보다 훨씬 많이 최적화 됐다..

나도 풀이할 때 저렇게 for로 재귀를 돌려야하나 싶었는데

나는 메인에 한번만 호출해야한는 고정관념에 갇히고말았다..

담에는 더 분발해야겠다!

 

그리고 자기 부모인덱스보다 높은 인덱스만을 재귀로 진행했다면 

또 다른 코드는 각 인덱스를 더할지, 말지 로 재귀를 진행하는 코드도 있었다.