글 읽기 - 흐..현자타임 오네요

kangsy763 4년 전 0

앞선 2630색종이 쿼드트리 문제에서 각 4 꼭지점 좌표를 다 주고, 나눌 때에 시작값과 끝 값을 더하고 /2 만 하면 만사오케이여서

이번 9개로 나누는 문제도 그렇게 했다가 값이 완전 다르길레 끙끙거리다가 겨우 풀었어요

이상하다 싶어서 구글에 찾아보니 완전히 다른 방법으로 풀더라구요..

쉬운문제를 이렇게 돌아서 가다니... 이제라도 어떤식으로 분할정복 푸는지 찾아본게 다행이네요 ㅠ ㅠ

#include <stdio.h>
using namespace std;
int map[2188][2188] = { 0 };

int m_cnt = 0, z_cnt = 0, o_cnt = 0;
void dq(int, int, int, int);

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	dq(1, n, 1, n);
	printf("%d\n%d\n%d", m_cnt, z_cnt, o_cnt);
	return 0;
}

void dq(int wf, int wl, int hf, int hl) {
	int standard = map[hf][wf];
	int check = 1;
	for (int i = wf; i <= wl; i++) {
		for (int j = hf; j <= hl; j++) {
			if (standard != map[j][i]) {
				check *= -1;
				break;
			}
		}
		if (check == (-1)) break;
	}
	if (check == 1) {
		if (standard == (-1)) m_cnt++;
		else if (standard == 0) z_cnt++;
		else if (standard == 1) o_cnt++;
	}
	else if (check == (-1)) {
		dq(wf, wf+(wl-wf)/3, hf, hf + (hl - hf) / 3);
		dq(wf+(wl-wf)/3+1, wf+(wl-wf)*2/3, hf, hf + (hl - hf) / 3);
		dq(wf+(wl-wf)*2/3+1, wl, hf, hf + (hl - hf) / 3);

		dq(wf, wf + (wl - wf) / 3, hf+(hl-hf)/3+1,hf+(hl-hf)*2/3);
		dq(wf + (wl - wf) / 3 + 1, wf + (wl - wf) * 2 / 3, hf + (hl - hf) / 3 + 1, hf + (hl - hf) * 2 / 3);
		dq(wf + (wl - wf) * 2 / 3 + 1, wl, hf + (hl - hf) / 3 + 1, hf + (hl - hf) * 2 / 3);

		dq(wf, wf + (wl - wf) / 3,  hf+(hl-hf)*2/3+1,hl);
		dq(wf + (wl - wf) / 3 + 1, wf + (wl - wf) * 2 / 3, hf + (hl - hf) * 2 / 3 + 1, hl);
		dq(wf+(wl-wf)*2/3+1, wl, hf + (hl - hf) * 2 / 3 + 1, hl);
	}
}

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

문제

문제

출처

ICPC

흐..현자타임 오네요

kangsy763 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말