글 읽기 - 시간초과 질문드립니다 답이 안보여요...

p_ce1052 3년 전 0

랜덤으로 다음과같이 50개일때로 백트래킹해도 잘 돌아가는데 시간초과가 납니다 ㅠㅠ 어디가 문제인가요?

dp[i]값을 정의하고 싶어도

앞에 어떤 사각형들을 골랐느냐에 따라 값이 달라지니까 dp도 안되고 이미 고른 상태에 따른 현재부터의 최댓값을 map에도 저장해봤는데 그쪽은

메모리 초과를 받았습니다 어떻게 해야할지 모르겠어요

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
long long unit = 1;
struct square{
	int l,r,u,d;
};
int n;
square arr[105];
long long not_compatible[105];
int maxscore;
long long maxstate;

void f(int curr,long long picked,int score){
	picked|=(unit<<curr);
	score+=curr;
	if(maxscore<score){
		maxscore = score;
		maxstate = picked;
	}
	for(int i=curr+1; i<=n; i++){
		if(not_compatible[i]&picked) continue;
		f(i,picked,score);
	}
}


int main(){
	srand(time(NULL));
	
	n = 50;
	for(int i=1; i<=n; i++){
		int a = rand()%1000+1;
		int b = rand()%1000+1;
		int c = rand()%1000+1;
		int d = rand()%1000+1;
		arr[i].l = min(a,c);
		arr[i].r = max(a,c);
		arr[i].d = min(b,d);
		arr[i].u = max(b,d);
	}
	
	
	
	
	for(int i=1; i<=n; i++){
		square&a = arr[i];
		for(int j=i+1; j<=n; j++){
			square&b = arr[j];
			if(a.l>b.r || b.l>a.r || a.d>b.u || a.u<b.d) continue;
			else{
				not_compatible[i]|=(unit<<j);
				not_compatible[j]|=(unit<<i);
			} 
		}
	}
	for(int i=1; i<=n; i++) f(i,0,0);
	long long temp = maxstate;
	long long ret = 0;
	while(temp){
		ret+=temp%2;
		temp/=2;
	}
	cout<<ret<<'\n';
	for(int i=1; i<=n; i++){
		if(maxstate&(unit<<i)) cout<<i<<" ";
	}
}

p_ce1052 3년 전 0

아 50개일 때 전혀 안겹치게 데이터를 만드니까 시간초과가 나네요.... 어떻게 고쳐야 할지 모르겠습니다... dp인가요?

pl0892029 3년 전 1

완전탐색 문제는 맞습니다만, 완전 탐색의 효율을 높여야합니다. (아주 많이...)

그래프로 이 문제를 바라봅시다. 서로 겹치거나 포함해서, 동시에 존재할 수 없는 사각형 후보들을 간선으로 연결해줍시다.

이 때 첫번째 관찰을 할 수 있습니다.

- 다른 사각형들과 연결되지 않은 사각형은 고르는게 최선입니다. (점의 점수는 자연수이기 때문에, 굳이 거를 필요가 없죠.)

사각형 후보 A와 후보 B가 인접해있을 경우, 우리는 3가지 중 하나밖에 선택할 수 없습니다.

- A를 고르거나

- B를 고르거나

- A, B 둘 다 포기하거나

두개의 경우를 고려하는 것은 복잡합니다. A 하나만 바라봤을 때 다음을 알 수 있죠.

- A를 고를 수 있는 경우 = A와 연결된 모든 사각형들의 선택을 포기함

- A를 고르지 않는 경우 = A와 연결된 사각형들을 여전히 "후보로 고려"

따라서 색깔 3개를 준비합시다. 흰색, 회색, 검정색으로요. 각 색깔은 다음과 같은 규칙으로 존재할 수 있습니다.

- 흰색과 연결된 사각형은 모두 검정색이어야 합니다.

- 회색 옆에는 회색 또는 검정색만이 존재할 수 있습니다.

- 검정색의 주변에는 회색 또는 흰색만이 존재할 수 있습니다

모든 사각형들을 초기에 회색이라고 가정합시다. 우리는 다음과 같은 반복을 통해 최대 점수를 얻을 수 있습니다.

1. 임의의 회색인 사각형 하나을 고릅니다.

2. 해당 사각형을 흰색으로 칠하고, 연결된 사각형들을 검정색으로 칠해줍니다.

3. 검정색으로 칠한 사각형들로 이동해줍니다.

4. 현재 위치는 검정색입니다. 연결된 회색인 사각형들로 이동해줍니다. (흰색, 검정색은 이미 색칠되었기 때문에 무시합니다.)

5. (1 ~ 4)의 과정을 반복하여 더 이상 색칠할 수 있는 사각형이 없을 때까지 진행합니다.

6. 퇴각 검색(Backtracking)하여 "흰색"으로 골랐던 점들을 이번에는 "검정"으로 표시해봅시다. (당연히 주변 사각형들의 색깔을 회색으로 돌려야 합니다.)

7. (1 ~ 6)의 과정을 역시 반복하여 더 이상 색칠할 수 있는 사각형이 없을 때까지 진행합니다.

이렇게 완전 탐색을 하면서 상태값을 잘 기록해놓았다면, 매우 효율적으로 가장 높은 점수와 조합을 구할 수 있습니다.

p_ce1052 3년 전 0

이런 풀이도 있군요 긴 글 감사합니다

지금 좌표 DP로 DP[I] = I 좌표 이후의 사각형들로 고를 수 있는 최대 개수. 로 짜고 있는데

말씀해주신 방법도 한 번 시도해보겠습니다

p_ce1052 3년 전 0

이 문제 혹시 bipartite matching 으로도 풀어낼 수 있는 문제인가요?

pl0892029 3년 전 0

이분 그래프란 흰색 - 검정색 의 색상이 인접한 노드들끼리 겹치지 않게 색칠할 수 있어야 합니다.

이 문제는 그것이 불가능합니다.

p_ce1052 3년 전 0

순수 어려운 백트래킹이군요...그래서 플래구나 감사합니다

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

문제

문제

출처

ICPC

시간초과 질문드립니다 답이 안보여요...

p_ce1052 3년 전 0

p_ce1052 3년 전 0

pl0892029 3년 전 1

p_ce1052 3년 전 0

p_ce1052 3년 전 0

pl0892029 3년 전 0

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말