글 읽기 - 1074 조건추가하면 정답 안하면 시간초과 되는게 궁금합니다

baepoce 2년 전 0

안녕하세요 코딩초보입니다

아래코드로 제출을하면 시간초과가 나는데

주석에있는 조건을 추가하면 정답이 됩니다

저조건을 추가해서 시간이득을 얻는예시가 무엇인지 궁금합니다

읽어주셔서 감사합니다

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;


int n, r, c, cnt = 0;
void solve(int x, int y, int size) {
	if (x == r && y == c) {
		cout << cnt;
		return;
	}

	if (size >= 2) {
		if (x + size > r && y + size > c) { //x>=r && y>=c 추가하면 정답 
			solve(x, y, size / 2);
			solve(x, y + size / 2, size / 2);
			solve(x + size / 2, y, size / 2);
			solve(x + size / 2, y + size / 2, size / 2);
		}
		else {
			cnt += size * size;
		}
	}
	else
		cnt++;

}
int main() {
	cin >> n >> r >> c;
	solve(0, 0, pow(2, n));

}

fnfn9947 1년 전 0

만약 n=3일때를 가정하고

1 2

3 4

분면으로 나뉘어 있고 정답이 3사분면에 있다면, 저 조건이 없다면 모든 분면을 재귀로 탐색하여 시간초과가 뜹니다. 하지만 저 조건을 추가하면 정답이 있는 사분면만 재귀로 탐색하고

나머지는 그냥 그 사분면의 사이즈 만큼을 cnt에 추가하여 그냥 넘어가게 됩니다.

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

문제

문제

출처

ICPC

1074 조건추가하면 정답 안하면 시간초과 되는게 궁금합니다

baepoce 2년 전 0

fnfn9947 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말