글 읽기 - 정답자분들의 알고리즘이 이해가 되지 않습니다.

temp 8년 전 1

상위 정답자분들을 보니 다 비슷한 알고리즘이더라구요.

근데 왜 이런식으로 작성하는건지 도무지 이해가 되지 않습니다.

아래는 한분의 정답인데요..

저기 f라는 함수는 도대체 어떤 알고리즘을 적용한것이며

d는 도대체 뭔가요... 상당히 효율적인 알고리즘인거 같아서 배우고 싶습니다.

원리가 뭔가요?

#include<iostream>
using namespace std;

int N;
int a[20][20];
int d1[30];

int max = -1;


int f(int n) {
	if (n >= 2 * N - 1) {
		return 0;
	}

	int max = -1;
	int y = n < N ? n : N - 1;
	int x = n < N ? 0 : n - (N - 1);
	cout << y << ' ' << x << endl;
	while (y >= 0 && x < N) {
		if (a[y][x] == 1 && d1[x - y + N] == 0) {
			d1[x - y + N] = 1;
			int m = f(n + 2) + 1;
			max = m > max ? m : max;
			d1[x - y + N] = 0;
		}
		x++;
		y--;
	}
	if (max < 0) max = f(n + 2);

	return max;
}

int main(void) {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &a[i][j]);
		}
	}

	printf("%d\n", f(0) + f(1));

	return 0;
}

yukariko 8년 전 6

체스판을 N * N의 격자가 아니라, 2N 개의 대각선으로 바라보는 방법입니다.

대각선으로 체스판을 보게 되면 다음 두가지 이점이 있습니다.

1. 현재 대각선에서 비숍을 하나만 놓고 다음 대각선으로 이동하면 됩니다.

2. 현재 대각선의 어떤 위치에 비숍을 놓을 수 있는가의 검사는 반대 방향의 대각선에 비숍이 놓여졌는지를 확인하는것으로 O(1)에 수행할 수 있습니다.

temp 8년 전 0

조금만 더 설명해주실수있나요?

yukariko 8년 전 11

비숍은 대각선으로만 진행하기 때문에 어떤 한 칸에 비숍을 놓게되면, 그 칸에 속하는 두개의 대각선은 더이상 놓을 수 없습니다.

그 사실을 이용해서 체스판을 한칸 한칸 바라보는게 아니라, 대각선 단위로 바라보는것입니다.

위 코드의 n이 어느 대각선인지를 결정해줍니다.

만약 / 방향의 대각선마다 한칸씩 놓는다고 가정하면, / 대각선의 개수는 2n - 1개가 존재하고, 한 대각선마다 하나의 비숍만 놓는다면

더 이상 현재의 / 대각선은 볼 필요가 없습니다.

현재의 / 대각선에 비숍을 한개 놓을 수 있는 위치를 찾아야하는데, 이것은 입력에서 주어진 장애물과 현재까지의 선택으로 인한 \ 방향의 대각선의 사용여부가 필요합니다.

위 코드의 a배열과 d1 배열이 이에 해당합니다.

각 칸에 대해 / 방향, \ 방향의 대각선의 위치를 한번에 계산할 수 있습니다. 위 코드의 x - y + N이 그 역할을 담당합니다.

이런식으로 진행하는데, 위 코드는 인접한 대각선끼리는 독립적이라는 사실을 이용하여 반으로 쪼개어 더해준것으로 최적화를 수행한것 같습니다.

sea5727 7년 전 0

정답자분들 코드는 어떻게 볼수있나요..?

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

문제

문제

출처

ICPC

정답자분들의 알고리즘이 이해가 되지 않습니다.

temp 8년 전 1

yukariko 8년 전 6

temp 8년 전 0

yukariko 8년 전 11

sea5727 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말