1R/2016 09 19

오늘의 문제

• 만들기

참가자

• 박인서

코드

15이원준

#include<iostream>
using namespace std;

int N;
int arr[129][129] = { 0, };
int ans[2] = { 0, };

void search(int x, int y, int num){
  //cout<< x << " " << y << " " << num << endl;
  if(num == 1){
    ans[arr[x][y]]++;
    return;
  }
  int allSame = true;
  int color = arr[x][y];
  for(int i = 0; i<num && allSame; i++){
    for(int j = 0; j<num && allSame; j++){
      if(arr[x+i][y+j] != color){
        allSame = false;
      }
    }
  }
  if(allSame){
    ans[color]++;
    return;
  }
  search(x, y, num/2);
  search(x+(num/2), y, num/2);
  search(x, y+(num/2), num/2);
  search(x+(num/2), y+(num/2), num/2);
}


int main(){
  cin>> N;
  for(int i = 0; i<N; i++){
    for(int j = 0; j<N; j++){
      cin>> arr[i][j];
    }
  }
  search(0,0, N);
  cout<< ans[0] << endl << ans[1] <<endl;
}

박인서

#include <iostream>
int a[130][130];
int cnt[2];

void divcon(int x1, int x2, int y1, int y2) {
	int col = a[x1][y1];
	bool flag = false;

	for (int i = x1; i < x2; i++) {
		for (int j = y1; j < y2; j++) {
			if (a[i][j] != col) {
				flag = true;
				break;
			}
		}
		if (flag) break;
	}

	if (flag) {
		int xm = (x1 + x2) / 2, ym = (y1 + y2) / 2;
		divcon(x1, xm, y1, ym);
		divcon(x1, xm, ym, y2);
		divcon(xm, x2, y1, ym);
		divcon(xm, x2, ym, y2);
	}
	else cnt[col]++;
}

int main()
{
	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			std::cin >> a[i][j];
	}
	
	divcon(0, n, 0, n);
	std::cout << cnt[0] << std::endl << cnt[1];
	return 0;
}

아이디어

박인서

• 색종이의 전체를 비교한 뒤에 안되면 중앙을 기준으로 4개의 색종이로 분해
• 계속해서 찾아나간 뒤 색이 같으면 그 색의 색종이 갯수를 증가시켜주면 된다.