글 읽기 - 1018 체스판 다시칠하기 제 코드의 시간복잡도가 궁금합니다.

10jobss 6년 전 0

제가 구현한 방식은

WBWBWBWB를 패턴 1, BWBWBWBW를 패턴 2

체스판 세로 길이를 N, 가로 길이를 M 이라고 할 때

좌상단의 좌표를 (i, j)로 8*8 체스판을 패턴1, 패턴2와 비교하는 방식으로 구현했습니다.

NM개의 좌표에 대해 모두 체스판을 만들 수 있는지 확인하고, true라면 cmp함수를 호출하는데

cmp 내부에 이중for문을 무시하고 (50에 비해 8은 작으니까??) O(NM*8*8) --> O(NM)인지 (아니면 N,M 상관없이 O(N²))

O(N⁴) (N=50이라 8을 무시할정도는 아니다?) 인지 모르겠습니다.

~~(크롬에서 질문 작성하는데 글자가 자꾸 씹히네요)~~

#include <cstdio>
#include <algorithm>
#define INF 987654321
using namespace std;
int n, m, ans = INF;
char a[50][50];
char p1[8][8] = { {'W','B','W','B','W','B','W','B'},
				  {'B','W','B','W','B','W','B','W' },
				  { 'W','B','W','B','W','B','W','B' },
				  { 'B','W','B','W','B','W','B','W' },
				  { 'W','B','W','B','W','B','W','B' },
				  { 'B','W','B','W','B','W','B','W' },
				  { 'W','B','W','B','W','B','W','B' },
				  { 'B','W','B','W','B','W','B','W' } };

char p2[8][8] = { { 'B','W','B','W','B','W','B','W' },
				  { 'W','B','W','B','W','B','W','B' },
				  { 'B','W','B','W','B','W','B','W' },
				  { 'W','B','W','B','W','B','W','B' },
				  { 'B','W','B','W','B','W','B','W' },
				  { 'W','B','W','B','W','B','W','B' },
				  { 'B','W','B','W','B','W','B','W' },
				  { 'W','B','W','B','W','B','W','B' } };
bool chk(int y, int x) {
	if (y + 7 >= n || x + 7 >= m) return false;
	return true;
}
int cmp(int y, int x) {
	int i, j, ret1 = 0, ret2 = 0;
	for (i = 0; i < 8; i++) {
		for (j = 0; j < 8; j++) {
			if (a[i + y][j + x] != p1[i][j]) ret1++;
			if (a[i + y][j + x] != p2[i][j]) ret2++;
		}
	}
	return min(ret1, ret2);
}
int main() {
	scanf("%d%d", &n, &m);
	int i, j;
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) scanf(" %c", &a[i][j]);
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			if (chk(i, j)) {
				ans = min(ans, cmp(i, j));
			}
		}
	}
	printf("%d", ans);
	return 0;
}

jh05013 6년 전 1

체스판의 크기가 8*8로 고정되어 있으므로 O(NM)이 맞습니다. 한편 8*8 대신 X*Y라고 주어지면 O(NMXY)가 됩니다.

10jobss 6년 전 0

@jh05013

설명 감사합니다!

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

문제

문제

출처

ICPC

1018 체스판 다시칠하기 제 코드의 시간복잡도가 궁금합니다.

10jobss 6년 전 0

jh05013 6년 전 1

10jobss 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말