[C++] 2447 : 별 찍기 - 10

실버 Ⅰ

 

#include <iostream>

int arr[128][128] = { 0, };
int N;
int blue = 0;
int white = 0;

void df(int x, int y, int n) {

	int half = n / 2;
	
	int cnt = 0;
	for (int i = x; i < x + n; i++) {
		for (int j = y; j < y + n; j++) {
			if (arr[i][j]) cnt++;
		}
	}

	if (cnt == 0) {
		white++;
	}
	else if (cnt == n * n) {
		blue++;
	}
	else {
		df(x, y, half);
		df(x + half, y, half);
		df(x, y + half, half);
		df(x + half, y + half, half);
		return;
	}

}

int main() {
	
	scanf("%d", &N);

	int in;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &in);
			if (in) arr[i][j] = 1;
		}
	}

	df(0, 0, N);
	printf("%d\n%d", white, blue);
}

 

분할 정복

문제 - 1 페이지

 

전부터 계속 풀고 싶었던 별 찍기 10..

알고 보니까 분할 정복 문제길래..

 

분할 정복 문제를 마침 몇 개 푼 참이라 풀 수 있을 것 같아서

헐레벌떡 달려가서 풀었다

 

전에 생각했을 때 어려웠던 점이

아까의 색종이 문제처럼 분할했을 때 탐색하는 네모가

왼쪽 끝이 0, 0에서 벗어나지 못하는 걸 고민했었는데

함수에 네모 왼쪽끝 인자를 넘겨주면 된다는 것을 깨닫고..

풀 수 있게 되었다

 

근데 검색해보니까 약간 수학적 규칙을 찾아서 푼 사람도 있는 것 같은데..

애초에 이 문제는 딱 생긴 게 분할 정복 문제이기도 하고.

그래서 그냥 재귀를 이용한 분할 정복 문제로 풀었다..

메모리를 많이 잡아먹고 코드도 길긴 하지만..

 

하긴 입력값인 3^k에서 k가 8이상의 수가 되면

그땐 수학적 규칙으로 푸는 수 밖엔 없겠네..

 

(다른 코드...)

#include <stdio.h>

int pa_(int N, int x, int y) {
    if (N == 1)
        return 1;
    if (x / (N / 3) == 1 && y / (N / 3) == 1)
        return 0;
    return pa_(N / 3, x % (N / 3), y % (N / 3));
}

int pa(int N) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            if (pa_(N, i, j))
                printf("*");
            else
                printf(" ");
        printf("\n");
    }
    return 0;
}

int main(void) {
    int N;

    scanf("%d", &N);

    pa(N);
    return 0;
}

이건 속도가 좀 더 오래걸리긴 하는데..

배열도 안써도 되고..

이렇게 푸는 방법도 있구나 해서..

신기하다

엄청 똑똑하게 푸는 방법이네

수학적 규칙을 찾아낸 것도 아니고 딱 분할 정복 재귀처럼 풀었네