3234. 준환이의 양팔저울

LEVEL D4

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw&categoryId=AWAe7XSKfUUDFAUw&categoryType=CODE

SW Expert Academy

 

처음에 완전탐색으로 풀었지만 시간초과가 발생하였다.

 

조건 하나를 추가하여 패스되었다.

 

left값이 최대값을 갱신하기 바로 전의 조합의 갯수를(N! * 2^N) 모두 한번에 더하여 재귀를 줄이는 방법이였다.

 

 

 

 

소스보기

 

#include <stdio.h>
int map[9];
int visited[9]; 
int fact[] = { 0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
int expon[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 };
int maxVal;
int N, answer = 0;
void solution(int right, int left, int count)
{
	if (count == N) {
		answer++;
		return;
	}
	if (left >= maxVal - left) {
		answer += expon[N - count] * fact[N - count];
		return;
	}
	for (int i = 0; i < N; i++) {
		if (visited[i] == 0) {
			visited[i] = 1;
			solution(right, left + map[i], count + 1);
			if (right + map[i] <= left)
				solution(right + map[i], left, count + 1);
			visited[i] = 0;
		}
	}
}
int main()
{
	int T;
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		scanf("%d", &N);
		maxVal = 0;
		for (int i = 0; i < N; i++) {
			scanf("%d", &map[i]);
			visited[i] = 0;
			maxVal += map[i];
		}
		answer = 0;
		solution(0, 0, 0);
		printf("#%d %d\n",tc, answer);
	}
}