글 읽기 - DFS로 짰는데 시간초과가 나요 도와주세요

nusung 7년 전 0

문제를 저대로 해석해서 DFS를 통해서 풀었습니다.

예제와 제가 만든 몇 개의 간단한 test case에 대해서는 통과하는데

체출하니까 시간초과가 발생합니다.

어디서 어떤 부분에 시간을 줄일 수 있을까요?

혹시 DFS로는 시간관계상 풀지 못하는 건가요?

#include<iostream>
using namespace std;

int T,W;

int a[1000];
int mx=-1;
void DFS(int pos, int sum, int move, int len){
	if(move == W){
		for(int i = len ; i < T ; i++){
			if(a[i] == (pos+1))
				sum++;
		}
		if(sum > mx) mx = sum;
		return;
	}
	if(len == T){
		if(sum > mx) mx = sum;
		return;
	}
	// 현재들어와서 자두 나무랑 내 위치가 같으면 횟수 증가
	if( (pos+1) == a[len]){
		sum++;
	}

	// pos 0 또는 1
	// move 횟수가 W보다 작아야 움직일 수 있다.
	// 경우의 수는 이번 len에서 움직이냐 아니냐
	
	DFS((pos +1) % 2, sum, move+1, len+1);
	
	DFS(pos, sum, move, len+1);

	
}


int main(){
	//cin >> T >> W;
	scanf("%d %d",&T, &W);
	for(int i = 0 ; i < T ; i ++){
		scanf("%d",&a[i]);
	}
	DFS(0, 0, 0, 0);
	printf("%d\n",mx);
}

zlzmsrhak 7년 전 1

dfs는 모든 경우를 다 탐색하기 때문에 T개의 빈공간에 W개의 움직임을 배치하는 경우의 수

즉 _TC_W 정도의 시간이 소요되고, 2초를 아득히 넘어가게 됩니다.

그래서 다른 접근 방법이 필요하고, 이 문제의 경우 DP를 사용하면 해결할 수 있습니다.

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

문제

문제

출처

ICPC

DFS로 짰는데 시간초과가 나요 도와주세요

nusung 7년 전 0

zlzmsrhak 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말