글 읽기 - 시간초과가뜨는데 가지치기 할수있는 경우가 또 뭐가있을까욤?ㅜ

minhas2 7년 전 0

안녕하세요

지금 줄다리기 문제 풀어보고있는데

자꾸 시간초과가 뜹니다 ㅜㅜ

가지치기를 덜한건지 아니면 코드가독성이 많이 떨어지는건지...

시간단축할수 있는부분이나 가지치기 할 수 있는경우가 뭐가있을까요??

백트랙킹너무 어렵습니당..

// Tug of War.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

const int MAXPEOPLE = 100;

int partition(int left, int right, short* weight) {
	int first = left;
	int pivot = weight[first];
	left++;

	while (left <= right) {
		while (weight[left] <= pivot && left < right) left++;
		while (weight[right] > pivot && left <= right) right--;

		if (left < right) {
			int temp = weight[right];
			weight[right] = weight[left];
			weight[left] = temp;
		}
		else break;
	}

	int temp = weight[first];
	weight[first] = weight[right];
	weight[right] = temp;

	return right;
}
void Quicksort(int left, int right, short* weight) {
	int index;
	if (left < right) {
		index = partition(left, right, weight);

		Quicksort(left, index - 1, weight);
		Quicksort(index+1, right, weight);
	}
}

int Allsom;
int dividedPeople;
int N;

int BackTracking(int& minimumMinus, short* weight, int count, int startIndex, int currentSum1) {
	int i;
	int returnValue;
	static short judgeDec_Inc;
	static short thisJudge;
	static bool tjSw;

	//검사
	if (count == dividedPeople - 1) {
		judgeDec_Inc = 0;
		tjSw = false;
	}
	if (count == dividedPeople) {
		int comMinus = abs(Allsom - currentSum1 - currentSum1);//한쪽합과 다른쪽합의 차잇값
		if (!tjSw) {
			tjSw = true;
			thisJudge = comMinus;
		}
		else {
			if (thisJudge < comMinus)
				return 0;
			else thisJudge = comMinus;
		}

		if (comMinus == 0) {
			minimumMinus = -1;
			return currentSum1;
		}
			if (minimumMinus > comMinus) { //작은경우
				minimumMinus = comMinus;//최소차이값 수정
				judgeDec_Inc = 1;
			return currentSum1;
		}

	}



	//조건충족 안된경우
	for (i = startIndex; i < N; i++)
	{
		returnValue = BackTracking(minimumMinus, weight, count + 1, i + 1, currentSum1 + weight[i]);
		if (returnValue == 0) return minimumMinus;
		if (minimumMinus == -1)
			break;
	}

	return minimumMinus;

}


int main()
{
	int TC;
	short* weight = new short[MAXPEOPLE];
	int minus;
	int result;

		Allsom = 0;
		
		cin >> N;
		dividedPeople = N / 2;

		for (int i = 0; i < N; i++)
		{
			cin >> weight[i];
			Allsom += weight[i];
		}
		minus = Allsom;

		Quicksort(0, N - 1, weight);

		BackTracking(minus, weight, 0, 0, 0);
		result = Allsom / 2 - minus / 2;

		printf("%d %d", result, Allsom - result);
	
    return 0;
}

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

문제

문제

출처

ICPC

시간초과가뜨는데 가지치기 할수있는 경우가 또 뭐가있을까욤?ㅜ

minhas2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말