글 읽기 - 흰색칸 검은칸 나누어서 작성했는데 시간초과가 나옵니다....

cmwmom 3년 전 0

다른 테스트 케이스들은 잘 되는데 자꾸 시간초과가 되네요.. 제가 사용한 방식에 어떤 문제가 있는지 궁금합니다 ㅠㅠ

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n;
int maxi, maxi2; 			//좌표의 합이 짝수인 비숍의 최대 개수, 홀수인 비숍의 최대 개수 
bool diag1[150];			//왼쪽 하단에서 오른쪽 상단으로의 대각선 
bool diag2[150];			//왼쪽 상단에서 오른쪽 하단으로의 대각선 
vector<pair<int, int> > v;	//좌표의 합이 짝수인 비숍의 좌표 
vector<pair<int, int> > v2;	//좌표의 합이 홀수인 비숍의 좌표 

//좌표의 합이 짝수인 비숍 
void func(int cur){
	for(int i = 0;i < v.size();i++){
		if(diag1[v[i].X+v[i].Y] || diag2[v[i].X-v[i].Y+n-1]) continue;
		maxi = max(maxi, cur);//최대 비숍의 수 
		diag1[v[i].X+v[i].Y] = true;
		diag2[v[i].X-v[i].Y+n-1] = true;
		func(cur+1);
		diag1[v[i].X+v[i].Y] = false;
		diag2[v[i].X-v[i].Y+n-1] = false;
	}
}

//좌표의 합이 짝수가 아닌 비숍 
void func2(int cur){
	for(int i = 0;i < v2.size();i++){
		if(diag1[v2[i].X+v2[i].Y] || diag2[v2[i].X-v2[i].Y+n-1]) continue;
		maxi2 = max(maxi2, cur);
		diag1[v2[i].X+v2[i].Y] = true;
		diag2[v2[i].X-v2[i].Y+n-1] = true;
		func2(cur+1);
		diag1[v2[i].X+v2[i].Y] = false;
		diag2[v2[i].X-v2[i].Y+n-1] = false;
	}
}

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	bool is_right = false;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++){
			int num;
			cin >> num;
			if(num){
				if((i+j)%2)
					v.push_back({i, j});
				else
					v2.push_back({i, j});
			}
		}
	}
	//비숍의 수가 없다면 실행하지 않는다. 
	if(v.size())
		func(1);
	if(v2.size())
		func2(1);
	cout << maxi + maxi2;
	return 0;
}

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

문제

문제

출처

ICPC

흰색칸 검은칸 나누어서 작성했는데 시간초과가 나옵니다....

cmwmom 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말