[백준] 2630번 색종이 만들기 C++ 문제풀이

https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

문제 풀이

분할 정복 문제였다.
N / 2로 나눠가면서 종이가 완성이 되는지를 확인했다.
맨 처음 제출하니 70%쯤에서 틀렸다고 나와서 생각을 해보니, 처음부터 완성된 종이를 준 경우를 처리하지 않았다.

따라서 처음 탐색 과정을 추가해 처음부터 종이가 완성된 경우는 0 1을 출력하고 아닌 경우는 분할 정복을 이용해 문제를 해결했다.

소스 코드

#include <iostream>
using namespace std;

int paper[129][129] = { 0 };
int one_cnt = 0; // 0이 적힌 종이수
int zero_cnt = 0; // 1이 적힌 종이수

void paper_div(int row, int col, int n); #종이를 N/2로 나누는 함수
void paper_cnt(int r, int c, int num); #종이가 완성된 경우 세는 함수


int main() {
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> paper[i][j];
		}
	}
	//모든 판이 하나의 숫자로 이루어져있는지 확인
	bool find = true;
	int a = paper[1][1];
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (paper[i][j] != a) {
				find = false;
				break;
			}
		}
	}
	if (find == true) { //하나의 숫자로 이루어진 경우
		if (a == 1) {
			cout << 0 << '\n';
			cout << 1 << '\n';
		}
		else {
			cout << 1 << '\n';
			cout << 0 << '\n';
		}
	}
	else { // 하나의 숫자로 이루어지지 않은 경우
		paper_div(1, 1, N);
		cout << zero_cnt << '\n';
		cout << one_cnt << '\n';
	}
}

void paper_div(int row, int col, int n) {
	if (n == 1) {
		return;
	}
	else {
		int num = n / 2;
		paper_cnt(row, col, num);
		paper_cnt(row + num, col, num);
		paper_cnt(row, col + num, num);
		paper_cnt(row + num, col + num, num);
	}
}

void paper_cnt(int r, int c, int num) {
	bool find = true;
	int a = paper[r][c];
	for (int i = r; i < r + num; i++) {
		for (int j = c; j < c + num; j++) {
			if (paper[i][j] != a) {
				find = false;
			}
		}
	}
    
	if (find == false) {
		paper_div(r, c, num); #하나로 이루어지지 않은 경우 
	}
	else {
		if (a == 1)
			one_cnt += 1;
		else
			zero_cnt += 1;
	}
}