코드 복사/붙여넣기 하는 당신이 아름답습니다.

1799 : 비숍

풀이

일반적인 풀이로 답을 구하려면 O(2^(10*10))으로 TLE가 난다.

체스판에서 대각선이 흑과 백으로 구분됨을 이용하자.

흑색칸 O(2^(5*5))와 백색칸 O(2^(5*5))를 따로 구해서 더하면 TLE를 피할 수 있다.

앞선 (boj 9663 N-Queen) 풀이에서 언급한 x를 +로 뒤집기(?)를 이용할 수 있겠다.

코드

#include <stdio.h>
#define max(a,b) (a)>(b)?(a):(b)

int n, f, ans[2], l[33], r[33], a[33][33];
void dfs(int x, int y, int c) {
	ans[f] = max(ans[f], c);
	if (y >= n) y = f ^ (++x % 2);
	if (x >= n) return;
	if (a[x][y] && !l[x + y] && !r[x - y + n]) {
		l[x + y] = r[x - y + n] = 1;
		dfs(x, y + 2, c + 1);
		l[x + y] = r[x - y + n] = 0;
	}
	dfs(x, y + 2, c);
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
		scanf("%d", &a[i][j]);
	dfs(0, 0, 0); f = 1;
	dfs(0, 1, 0);
	printf("%d", ans[0] + ans[1]);
	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-11-01 11:59

Read more posts by this author