글 읽기 - [2628] 분할정복(?)으로 풀었는데요 시간초과가 납니다.

jeongbeen 3년 전 0

제가 재귀랑 분할정복을 굉장히 못해서...

코드가 잘못돼서 시간초과가 나는거 같은데, 어디서 막히는지 모르겠습니다.

cut(0 10 0 8) 부터 시작해서
cut(0 10 0 3)
cut(0 4 0 3)
cut(4 10 0 3)
cut(0 10 3 8)
cut(0 4 3 8)
cut(4 10 3 8)

이렇게 하나하나 쪼개어가면서 넓이를 구하도록 짰습니다.

어떻게 수정해야할까요?

힌트 부탁드립니다.

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
typedef pair<int, int> pi;

vector<pi>arr;
int n,m, t;
int maxx = -1;

//arr[idx]		가로 시작점/가로 끝점/세로 시작점/세로 끝점
void cut(int idx, int sx, int dx, int sy, int dy) {
	if (idx == t) {//arr순회 완료
		int s = (dx - sx) * (dy - sy); //넓이를 구함
		maxx = max(s, maxx); 
		return;
	}

	//가로로 자를 경우
	if (arr[idx].first == 0) { 
		if(arr[idx].second < dy)
			cut(idx + 1, sx, dx, sy, arr[idx].second); //cut(4 10 3 1) << 이런 경우를 막기 위함
		else cut(idx + 1, sx, dx, sy, dy);
		
		if(sy < arr[idx].second)
			cut(idx + 1, sx, dx, arr[idx].second, dy);
		else cut(idx + 1, sx, dx, sy, dy);

	}

	//세로로 자를 경우
	else {
		if (arr[idx].second < dx)
			cut(idx + 1, sx, arr[idx].second, sy, dy);
		else cut(idx + 1, sx, dx, sy, dy);


		if (sx < arr[idx].second)
			cut(idx + 1, arr[idx].second, dx, sy, dy);
		else cut(idx + 1, sx, dx, sy, dy);

	}
}

int main() {
	scanf("%d%d", &m, &n);
	scanf("%d", &t);
	for (int i = 0; i < t; i++)
	{	
		int a, b;
		scanf("%d %d", &a, &b);
		arr.push_back({ a,b });
	}

	cut(0, 0, m, 0, n);

	printf("%d", maxx);
}

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

문제

문제

출처

ICPC

[2628] 분할정복(?)으로 풀었는데요 시간초과가 납니다.

jeongbeen 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말