2630 색종이 만들기

백준 2630 색종이 만들기 :  https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

분할 정복 문제는 간단히 말하면,

문제를 나누어 풀어 작은 문제의 답을 구해 그 답을 합치면서 최종 문제의 답을 구하는 것

즉, 재귀로 풀면 좋을 것

 

[문제를 풀기 전 생각한 것 ]

① n/2가 1이 될 때 까지 나누고 합치면서 값을 계산할 것

② 재귀 함수 구성

• 정사각형을 1, 2, 3, 4로 나누기 (순서는 아래 그림 참고)
• 1, 2, 3, 4가 가리키는 값이 같으면 return을 그 값으로 할 것
• 값이 다르면, 각 번호가 가리키는 색의 색종이 값 증가 및 return 값을 0, 1이 아닌 수로 할 것

정사각형 번호

 

[문제 풀이]

#include <iostream>
using namespace std;


int cut(int** c_paper, int size, int n, int x, int y, int(&num)[2]) { // 색종이 자르기 
	int dn = n / 2;

	if (dn < 1) return c_paper[x][y];

	int one = cut(c_paper, size, dn, x, y, num);
	int two = cut(c_paper, size, dn, x, y + dn, num);
	int three = cut(c_paper, size, dn, x + dn, y, num);
	int four = cut(c_paper, size, dn, x + dn, y + dn, num);

	if (one == two && two == three && three == four) {
		if (size == n && one != 2) num[one]++;
		return one;
	}
	else {
		if (one != 2) num[one]++;
		if (two != 2) num[two]++;
		if (three != 2) num[three]++;
		if (four != 2) num[four]++;
		return 2;
	}


	
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	int** c_paper;
	c_paper = new int*[n]; // 배열 할당
	for (int i = 0; i < n; i++) { 
		c_paper[i] = new int[n];
	}

	int k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> k;
			c_paper[i][j] = k; // 값 저장
		}
	}

	int num[2] = {0, 0}; //0 : white, 1 : blue

	cut(c_paper, n, n, 0, 0, num); // 색종이 자르기 

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


	for (int i = 0; i < n; i++) { // 배열 삭제
		delete[] c_paper[i];
	}
	delete[] c_paper;

	return 0;
}

int** c_paper		색종이 색을 저장하는 배열
int num[2]		색종이 색별 개수를 저장하는 배열로 0은 하얀색, 1은 파란색 개수를 저장
int cut(int** c_paper, int size, int n, int x, int y, int(&num)[2])	int size	전체 종이의 한 변의 길이
	int n	현재 확인하는 종이의 한 변의 길이
	int x, int y	1, 2, 3, 4 위치를 구분하기 위한 위치 정보
	① 한 변의 길이가 1보다 작은 경우 현재 위치값 return ② 정사각형을 네 개로 나누어 각각 확인 ③ 네 개의 값이 모두 동일하면 현재 값 return (단, 현재 한 변의 길이가 전체 종이의 한 변의 길이면 num을 증가시키고 return) ④ 값이 다르면, 각자 저장된 값에 대한 num 증가 후 0,1이 아닌 2를 return  주의) num이 2인 경우 배열 값이 증가되지 않도록

 

[comment]

생각보다 쉽게 풀린 문제 였다.

다 풀고나니 그냥 num 배열을 num[3]으로 설정했으면, 따로 조건 설정을 안했어도 됐겠다는 생각이..