글 읽기 - 재귀) 어떻게하면 시간초과를 해결할수 있을까요...

wnsrnek3 6년 전 0

웬만한 예제는 잘 통과하는 것을 보고, 나름 근사하게 짰다고 생각했는데,

N이 꽤 크고 r,c이 어느정도 크면 터져버리네요..

결국 시간초과가 뜨는데..

어떻게 해결하면 좋을까요....??ㅠㅠ 조언좀 부탁드립니다

#include <cstdio>
#include <algorithm>
int count=0, r, c;
void explore(int row, int column, int len) {
	if (len==1) {
		if (r==row&& c==column) {			
			printf("%d", count);
			exit(0);
		}
		count++;
	}
	else {		
		explore(row, column, len/2);		
		explore(row, column+len, len/2);
		explore(row+len/2, column, len/2);
		explore(row+len/2, column+len/2, len/2);
	}
}
int main() {
	int n; scanf("%d", &n);
	scanf("%d%d", &r, &c);
	explore(0, 0, (int)pow(2, n));
	return 0;
}

chogahui05 6년 전 1

작은 TC에 대해서 돌려보셨나요?

N이 2일 때 0<=r<4, 0<=c<4을 만족하는 r,c를 모두 넣어보고 돌려보니까

제대로 결과값이 나오지 않던데요.

바로 보이는 것은 14번째 줄이네요~

chogahui05 6년 전 1

그리고 N이 꽤 큰 수일 때 터져버리는 이유는

탐색할 필요가 없는 가지를 탐색하기 때문입니다. 이 부분만 잘 고쳐보세요.

wnsrnek3 6년 전 0

@chogahui05

답변대단히 감사합니다!!

죄송합니다!! 코드 수정해서올리는 과정에서 오타가 있었네요 ㅠ

말씀하신부분 len/2로 하면 결과는 잘 나오지만 크면 터져버리더라구요...

@chogahui05

감사합니다!! 말씀하신대로 탐색할필요없는부분은 갯수만 세서 count에 더해주는걸로 끝내버리니 시간초과문제가 해결되네요!

#include <cstdio>
#include <algorithm>
int count=0, r, c;
void explore(int row, int column, int len) {
	if (len==1) {
		if (r==row && c==column) {			
			printf("%d", count);
			exit(0);
		}
		count++;
	}
	else {	
		if (abs(r-row)>=len/2 || abs(c-column)>=len/2)
			count += len*len/4;
		else
			explore(row, column, len/2);
		
		if (abs(r-row)>=len/2 || abs(c-len/2 -column)>=len/2)
			count += len*len/4;
		else
			explore(row, column+len/2, len/2);

		if (abs(r-row-len/2)>=len/2 || abs(c -column)>=len/2)
			count += len*len/4;
		else
			explore(row+len/2, column, len/2);

		if (abs(r-row-len/2)>=len/2 || abs(c-len/2 -column)>=len/2)
			count += len*len/4;
		else
			explore(row+len/2, column+len/2, len/2);
	}
	//탐색하지 않아도 되는 곳은 보질 말자!
}
int main() {
	int n; scanf("%d", &n);
	scanf("%d%d", &r, &c);
	explore(0, 0, (int)pow(2, n));
	return 0;
}

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

문제

문제

출처

ICPC

재귀) 어떻게하면 시간초과를 해결할수 있을까요...

wnsrnek3 6년 전 0

chogahui05 6년 전 1

chogahui05 6년 전 1

wnsrnek3 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말