글 읽기 - 1799 질문드립니다~

algospot 8년 전 0

시간초과 흠..

효율적인 가지치기의 방법이 어떤게 있을까요..

아니면 가지치기 이전에 아에 방법을 뜯어고쳐야하는지..

참고로 제 방법은, 대각선에 번호를 붙여 총 4*N-2개의 대각선에 대해 N*N맵을 돌면서 놓을지 말지를 결정하는 dfs식입니다..

#include <stdio.h>
int N;
int d[15][15];
int cross[50];
int check[50];
int best;
void dfs(int y, int x, int cnt) {
	if(y==N) return;
	if(d[y][x]==1 && !cross[y+x] && !cross[2*N-1+(2*N-1)/2+(x-y)]) {
		cross[y+x]=1;
		cross[2*N-1+(2*N-1)/2+(x-y)]=1;
		dfs(y+(x+1)/N,(x+1)%N,cnt+1);
		cross[y+x]=0;
		cross[2*N-1+(2*N-1)/2+(x-y)]=0;
	}
	dfs(y+(x+1)/N,(x+1)%N,cnt);
}
int main(void) {
	int i,j,k;
	scanf("%d",&N);
	for(i=0;i<N;i++) {
		for(j=0;j<N;j++) {
			scanf("%d",&d[i][j]);
		}
	}
	best=0;
	dfs(0,0,0);
	printf("%d\n",best);
	return 0;
}

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

문제

문제

출처

ICPC

1799 질문드립니다~

algospot 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말