(백준 1182번 부분수열의 합 C++) 라이님 블로그 대회 알고리즘 따라잡기 2) 완전탐색(Brute-force Search) 6탄

이 기세를 몰아 크리스마스 특집으로 하나 더! 부분수열의 합을 풀고자 한다.

 

  완전탐색 시리즈는 여기↓  

2023.12.25 - [알고리즘] - (백준 1018번 체스판 다시 칠하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 2) 완전탐색(Brute-force Search) 5탄

(백준 1018번 체스판 다시 칠하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 2) 완전탐색(Brute-force

 

1182번 부분수열의 합

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

1182번: 부분수열의 합

 

이 문제는 좀 잘 푼 것 같아서 풀이를 자세히 써볼까 한다 히힛☺️

 

문제 풀이과정

우선 쉬운 예시로 생각해보자. 우리에게 4개의 숫자1, -1, 3, 4가 주어졌다고 생각하자. 그러면 2^4개의 경우의 수가 나온다. 

물론 이렇게 푸는게 국룰이기는 하지만.. 조금만 더 규칙성있게 만들면 부분합은 아래와 같이도 구할 수 있을 것이다. 

1  을 기준으로 생각하면 배열 8~15까지 대입하고           (여기서 8 = 2^(4-1))

-1 을 기준으로 생각하면 배열 4~7, 12~15                       (여기서 4 = 2^(4-2))

3  을 기준으로 생각하면 배열 2~4, 6~7, 10~11, 14~15    (여기서 2 = 2^(4-3))

4  을 기준으로 생각하면 배열 1, 3, 5, 7, 9, 11, 13, 15      (여기서 1 = 2^(4-4))

 

 

오예 규칙성이 보인다! 이를 일반적인 경우에 대해 작성해보자. 

 

N개의 숫자의 부분합은 2^N개의 경우의 수가 있다. 이 경우 2^N개의 경우의 수를 모두 고려해야 하는데, 

동적할당으로 2^N개의 원소를 가지는 배열Arr을 만들고, input은 배열을 반으로 쪼개는 방식으로 더했다. 

결과로 보면 더욱 이해하기 쉽다.

 

예제는 문제에 있는 예제를 그대로 사용했다.(N=5, 배열 -7, -3  2, 5, 8) 

i = 0일 때 input -7이 들어왔다.

그 다름 i = 1일때 input -3이 들어왔는데 두 번에 걸쳐서 더해지는 모습을 알 수 있다.

i = 2일 때 input으로 -2가 들어왔다. 이는 네 번에 걸쳐서 더해진다는 걸 알 수 있다.

i = 3일 때 input은 5가 들어왔고, 이는 8번에 걸쳐서 더해진다.

마지막으로 i = 4일 때 input은 8가 들어왔고, 이는 16번에 걸쳐서 더해진다.

🚨Arr[0]의 경우 아무런 숫자로 더해지지 않았기 때문에 생기는 0이므로 제외하여야 한다!!!🚨

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cmath>

void Adder(int N, int i,  int * Arr, int temp);
int main() {
	int N, S; int temp; int ans = 0;
	scanf("%d %d", &N, &S);
	int LEN = (int) std::pow(2, N);
	int* Arr = new int[LEN] {0};

	for (int i = 0; i < N; i++) {
		scanf("%d", &temp);
		Adder(N, i, Arr, temp);
	}
	// i = 1 부터 시작하는 이유 : 
	// Arr[0]은 길이가 0인 부분수열
	// 문제에서는 길이가 양수인 부분수열만을 고려함
	for (int i = 1; i < LEN; i++) if (Arr[i] == S) ans++;
	
	printf("%d", ans);
	return 0;
}
void Adder(int N, int i, int* Arr, int temp) {
	int sp = (int) std::pow(2, N -1 - i); // starting point
	int cnt = 1;
	int cp = sp; // current point
	while (cp < ((int) std::pow(2, N))) {
		for (int j = cp; j < cp+sp;  j++) Arr[j] += temp;
		cp += 2 * sp;
	}
	return;
}

 

 

아니 근데 과거의 나는 더 똑똑했었다

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

재귀함수를 사용할 줄 아는 문명인이라니..😶 

과거의 내 코드도 배울 점이 많구나

#include <iostream>
using namespace std;

// 완전탐색 문제 - 재귀함수를 이용할 것


int Arr[20];
int N,S;
int cnt = 0;

//완전탐색 함수만들기
void Search(int index, int sum){
	int temp = sum + Arr[index];
	if (index >= N) return ;
	if (temp == S) cnt ++;
	Search(index + 1, sum);
	Search(index + 1, temp);
}


int main(){
	
	scanf("%d %d",&N,&S);

	for(int i=0;i<N;i++) scanf("%d",&Arr[i]);

	Search(0,0);

	printf("%d", cnt);

}