글 읽기 - 시간초과 질문입니다.. 부탁드립니다

lwh1992 4년 전 0

16,24 번줄 그리고 num을 이용해서 오름차순으로 한다고 생각했는데 계속 시간초과가 발생합니다..

혹시 뭐가 잘못된건지 알려주시면 감사하겠습니다!!

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int n,min=0;
int arr[20][20];
bool c[20];

void go(int x,int num) {
	if (n / 2 == x) {
		int s = 0, r = 0;
		for (int i = 0; i < n; i++)
		{
			
			if (c[i]) { //check 배열 TRUE
				for (int j = i + 1; j < n; j++)
				{
					if (c[j]) {
						s += (arr[i][j] + arr[j][i]);
					}
				}
			}
			else {//check 배열 false
				for (int j = i + 1; j < n; j++)
				{
					if (!c[j]) { //i보다 큰 check 하지 않은 배열.
						r += (arr[i][j] + arr[j][i]);
					}
				}
			}
			
		}

		if (s - r >= 0 && s - r < min) {
			min = s - r;
		}
		else if (r - s >= 0 && r - s < min) {
			min = r - s;
		}

		return;
	}
	for (int i = num; i < n; i++)
	{
		if (!c[i]) {

			c[i] = true;
			go(x + 1,num+1);
			c[i] = false;

		}
				
	}
}
int main() {
	
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &arr[i][j]);
		}
	}
	min = 2000;

	go(0,0);

	printf("%d\n", min);

	return 0;
}

ha_ram 4년 전 0

10번과 11번째 줄 사이에

for(int i=0; i<n; i++){

if(c[i]) printf("%d ",i);

}

printf("\n");

를 추가한다음 예제입력 2번을 돌려보시면

이미 탐색한 것을 중복되게 탐색하는것을 알 수 있으실 겁니다.

중복탐색을 없애시면 될것 같습니다.

그리고 한가지 팁을 더 드리자면 6명의 참가자가 있다고 할 때

스타트팀 : 1 2 3, 링크팀 : 4 5 6 이렇게 구성되어 능력치 차이를 구하는 것과

스타트팀 : 4 5 6, 링크팀 : 1 2 3 이렇게 구성되어 능력치 차이를 구하는 것은 같습니다.

그러므로 스타트 팀에 1 2 3 을 넣어서 능력치 차이를 구했다면 나중에 스타트팀에 4 5 6을 넣어서 능력치 차이를 구해볼 필요는 없습니다.

lwh1992 4년 전 1

조언 감사합니다. 다시 해보겠습니다.ㅠㅠ!!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 질문입니다.. 부탁드립니다

lwh1992 4년 전 0

ha_ram 4년 전 0

lwh1992 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말