[Baekjoon] 2630번: 색종이 만들기

🥅 문제

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

 

🔍 설계

현재 색종이의 모든 칸의 색이 같지 않으면 4등분해 나가는 문제이다. 재귀로 해결할 때의 시간 복잡도를 계산해보면, O(2^7*2^7+2^6*2^6*2^2+2^5*2^5*2^2*2^2...)=O(2^14*8)=O(2^17)이므로, 시간 제한 1초 내에 해결할 수 있다.

 

재귀함수에 시작점과 현재 색종이의 변의 길이를 전달한다. 칸의 색이 하나라도 다르면 잘라야 하기 때문에 비교 대상은 시작점의 색으로 하였다.

 

현재 색종이의 모든 칸을 확인하면서 다른 색을 가진 칸이 있다면, 4등분한 색종이를 나타내는 재귀함수를 실행한다.

현재 색종이의 모든 칸을 확인하면서 다른 색을 가진 칸이 없다면, 시작점의 색과 모두 같다는 의미이므로, 시작점의 색을 가진 색종이 수를 증가시킨다. 0은 하얀색, 1은 파란색이다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;	
int n;
vector<vector<int>> paper(128, vector<int>(128));
vector<int> result(2);

void slice(int start_x, int start_y, int length){
	int color = paper[start_x][start_y];
	for (int i=start_x; i<start_x+length; i++){
		for (int j=start_y; j<start_y+length; j++){
			if (color != paper[i][j]){
				slice(start_x, start_y, length/2);
				slice(start_x+length/2, start_y, length/2);
				slice(start_x, start_y+length/2, length/2);
				slice(start_x+length/2, start_y+length/2, length/2);
				return;
			}
		}
	}
	result[color] += 1;
	return;
}


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	cin >> n;
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			cin >> paper[i][j];
		}
	}
	slice(0, 0, n);
	cout << result[0] << "\n" << result[1] << "\n";
	return 0;
}

 

📝 메모

1074번 Z와 비슷한 문제