[백준 2630] 색종이 만들기 (C++/Python)

백준 1780 종이의 개수 (https://pinguovo.tistory.com/328) 문제와 풀이방법이 동일하다

 

---

 

C++)

#include <iostream>
#define MAX_NUM 128
using namespace std;

int arr[MAX_NUM][MAX_NUM];
int ans[2];

bool check(int x, int y, int len) {
	for (int i = x; i < x + len; i++) {
		for (int j = y; j < y + len; j++) {
			if (arr[x][y] != arr[i][j])
				return false;
		}
	}
	return true;
}

void func(int x, int y, int len) {
	if (check(x, y, len)) {
		ans[arr[x][y]]++;
		return;
	}

	int temp = len / 2;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++)
			func(x + i * temp, y + j * temp, temp);
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];
	}

	func(0, 0, n);

	cout << ans[0] << "\n" << ans[1];

	return 0;
}

 

 

 

Python)

import sys
read = sys.stdin.readline

n = int(read().rstrip())
arr = [ [0] * n for _ in range(n)]
ans = [0] * 2

def check(x, y, len):
    for i in range(x, x + len):
        for j in range(y, y + len):
            if arr[i][j] != arr[x][y]:
                return False
            
    return True

def func(x, y, len):
    if check(x,y,len):
         ans[arr[x][y]] += 1 
         return
    
    temp = len//2

    for i in range(2):
        for j in range(2):
            func(x + i*temp, y + j * temp, temp)

for i in range(n):
    arr[i] = list(map(int, read().rstrip().split()))

func(0,0,n)

for i in ans:
    print(i)