2817. 부분 수열의 합 - D3

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7IzvG6EksDFAXB

불러오는 중입니다...

이 문제는 조합과 백트래킹을 필요로 하는 문제입니다. 그럼 바로 보도록 하겠습니다.

---

N개의 숫자를 조합해서 K의 수를 표현할 수 있는 가지수를 나타내는 문제입니다.

 

그렇다면 당연히 조합이 필요하겠죠?

 

또한, N이 20을 넘어가기 때문에 1 ~ 20개의 숫자를 조합으로 구하려고 하는 것은 대단히 오래걸리기에 백트래킹을 사용해야합니다. 지금까지 더한 합이 K를 넘기면 안된다는 조건으로요.

 

#include <stdio.h>
#include <malloc.h>

void combi(int* arr, int st, int cnt, int temp, int depth);
int* vis;
int N, K, result;

int main(void) {
	int T;
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		// 입력
		scanf("%d %d", &N, &K);
		int* arr = (int*)malloc(sizeof(int) * N);
		for (int n = 0; n < N; n++) {
			scanf("%d", &arr[n]);
		}

		// 풀이
		result = 0;
		vis = (int*)malloc(sizeof(int) * N);
		for (int n = 1; n <= N; n++) {
			for (int j = 0; j < N; j++) {
				vis[j] = 0;
			}
			combi(arr, 0, 0, 0, n);
		}
		printf("#%d %d\n", t, result);
	}
}

void combi(int* arr, int st, int cnt, int temp, int depth) {
	if (cnt == depth) {
		if (temp == K) result++;
		return;
	}
	else if (temp > K) return;
	else {
		for (int i = st; i < N; i++) {
			if (vis[i] == 1) continue;
			vis[i] = 1;

			combi(arr, i, cnt + 1, temp + arr[i], depth);
			vis[i] = 0;
		}
	}
}

주의 깊게 봐야할 곳은 combi라는 함수입니다.

 

분기점이 총 3가지가 있습니다. 원하고자하는 조합 갯수를 만족했을 때, 지금까지 더한 합이 K를 넘겼을 때 (백트래킹), 이 두 가지가 아닌 경우

 

3개의 조합을 했을 때, 그 합이 구하고자 하는 값과 같다면, 갯수를 하나 증가시켜주면 됩니다.

 

여기서 주의깊게 봐야할 곳은 for문과 vis 배열입니다. for문의 시작 부분을 보면 st라는 인수를 시작점으로 하고 있습니다. vis는 combi 함수의 전역으로 사용되고 있습니다.

 

이 부분을 설명 드리자면, 총 4가지의 수 중 2개를 뽑는 조합을 시도했을때

1 1 0 0
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 1
0 0 1 1

이런식으로 나옵니다. 여기서 0번 인덱스를 살펴보면 0번 인덱스에서 나올 수 있는 조합의 수를 파악을 한 뒤엔, 절대 다시 한 번 1이 나오면 안됩니다. (이 부분을 vis가 합니다) 또한, 시간 단축을 위해 for 문의 시작 지점을 0이 아닌 인자 st를 사용하면서 조합을 찾는 위치를 기억할 수 있습니다.

 

이런 식으로 조합을 사용하여 문제를 풀었습니다.

 

아래는 조금더 간소화 해보았습니다.

#include <stdio.h>

void combi(int n, int r, int st);

int vis[5];

int main(void) {
	for (int i = 1; i <= 5; i++) {
		for (int j = 0; j < 5; j++) {
			vis[j] = 0;
		}
		combi(5, i, 0);
	}
}

void combi(int n, int r, int st) {
	if (r == 0) {
		for (int i = 0; i < n; i++) {
			printf("%d ", vis[i]);
		}
		printf("\n");
	}
	else {
		for (int i = st; i < n; i++) {
			if (vis[i] == 0) {
				vis[i] = 1;
				combi(n, r - 1, i);
				vis[i] = 0;
			}
		}
	}
}

---

사실 제가 한 방법은 배열을 이용한 조합입니다. vis라는 배열을 사용하며, for문으로 순회까지 하는 조합이니까요.

 

근데, 사실 문제를 되돌아보면, 저희가 궁금한 건 어떻게 조합의 결과과 궁금한 것이 아니라, 조합된 값들의 합입니다.

 

즉, 각 숫자들이 더해지는지 혹은 더해지지 않는지만 생각하면 문제를 쉽게 해결할 수 있다는 뜻입니다.

 

#include <stdio.h>
#include <malloc.h>

void sol(int idx ,int sum);

int N, K, answer;
int* arr;

int main(void) {
	// 입력
	int T;
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		scanf("%d %d", &N, &K);
		arr = (int*)malloc(sizeof(int) * N);
		for (int n = 0; n < N; n++) {
			scanf("%d", &arr[n]);
		}

		// 풀이
		answer = 0;
		sol(0, 0);
		printf("#%d %d\n", t, answer);
	}
}

void sol(int idx, int sum) {
	if (idx == N || sum > K) {
		if (sum == K) answer++;
		return;
	}
	sol(idx + 1, sum + arr[idx]);
	sol(idx + 1, sum);
}

 

 

이 방법은 아까 전의 방법보다 10배 빠른 속도를 보여주는 코드입니다.

---

이상 2817. 부분 수열의 합 - D3였습니다. ^_^