글 읽기 - recursive하게 짜보았는데 시간초과가 납니다.

gnujoow 8년 전 0

그냥 루프로 풀었을 때는 결과가 잘 나왔습니다.

재귀적으로 짜는것을 연습하고자 재귀함수로 짜보았는데요.

시간초과가 납니다.

함수를 호출하는 시간때문에 시간초과가 나는걸까요..?

//https://www.acmicpc.net/problem/2528
//2016.04.14

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

int N, L;
int t = 0;
int * start, * end, * dir;

void move(int pos);

int main(){
	scanf("%d %d",&N,&L);

	start = (int *)malloc(sizeof(int)*L);
	end = (int *)malloc(sizeof(int)*L);
	dir = (int *)malloc(sizeof(int)*L);

	//각 층에 대한 길이와 방향
	for(int i =0 ; i < N ; i++){
		int len;
		scanf("%d %d", &len, &dir[i]);
		if(!dir[i]){
			start[i] = 0;
			end[i] = len;
		}
		else{
			end[i] = L;
			start[i] = L-len;
		}
	}
	move(0);
	printf("%d\n",t);

	free(start);free(end);free(dir);
	return 0;
}


void move(int pos){
	if (pos == N-1)
		return;
	else if(!(end[pos] < start[pos+1] || start[pos] > end[pos+1]))
		return move(pos +1);

	t++;
	for(int i = pos ; i < N ; i++){
		if(!dir[i]){//정방향
			start[i]++;
			end[i]++;
			if(end[i] == L)
				dir[i] = 1;
		}
		else{//역방향
			start[i] --;
			end[i] --;
			if(start[i] == 0)
				dir[i] = 0;
		}
	}
	return move(pos);
}

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

문제

문제

출처

ICPC

recursive하게 짜보았는데 시간초과가 납니다.

gnujoow 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말