글 읽기 - 백트래킹으로 풀고 있는데 시간초과가 발생합니다

sm970124 6년 전 0

어디를 더 가지치기 해야할까요??

#include<stdio.h>
int cc[9][8], box[9], k, hap;
int n1;
int count;
void bt(int num, int floor)
{
	int i, m;
	if (floor == n1+1)
	{
		count++;
		return;
	}
	if (num == box[floor])
	{
		bt(0, floor + 1);
		return;
	}
	m = cc[floor][num] > cc[floor - 1][num + 1] + 1 ? cc[floor][num] : cc[floor - 1][num + 1] + 1;
	for (i = m; i <= k; i++)
	{
		cc[floor][num + 1] = i;
		bt(num + 1, floor);
	}
	return;
}
int main()
{
	int i,j;
	while (1)
	{
		count = 0;
		hap = 0;
		if (scanf("%d", &n1) == EOF)return 0;
		for (j = 1; j <= n1; j++)
		{
			scanf("%d", &box[j]);
			hap += box[j];
		}
		scanf("%d", &k);
		for (j = 1; j <= k-n1+1; j++)
		{
			cc[1][1] = j;
			bt(1, 1);
		}
		printf("%d\n", count);
	}
}

sgchoi5 6년 전 1

nwerc 문제는 대회에서 사용했던 TC 가 공개되어 있으니 한 번 써보세요..

http://gooddaytocode.blogspot....

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

문제

문제

출처

ICPC

백트래킹으로 풀고 있는데 시간초과가 발생합니다

sm970124 6년 전 0

sgchoi5 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말