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

2630번: 색종이 만들기

 

 

문제!

---

 

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

---

요약하면 계속해서 색종이를 잘라서 같은 색의 색종이로 이루어진 덩어리가 몇개씩 생기는지를 구하는 문제입니다!

 

그렇게 막 어려운 알고리즘이 아닌 단순 재귀를 통해서 계속 반복하여 풀어줄 수 있을것 같아서 풀어보았더니 

풀렸네요.... 쉬운문제인것 같습니다.

 

 

그럼 시작!

---

 

입력 받는 부분은 평소대로 받아 주었습니다.

cin >> N;

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

	cal(0, 0 ,N);

 

 

그리고 여기서 재귀를 일으켜줄 cal 함수를 하나 만들었는데

 

구조는 간단합니다. 시작점과 길이를 넣어주면 그 정사각형 안의 1의 갯수를 세어주어

하나의 큰 색종이가 만들어지는지를 판별하여 

만들어진다 >> 어떤색인지 판별하여 +=1

안만들어지면 4등분하여 만들어 줍니다... 

void cal(int y,int x, int count) {// 시작점, 한변 길이

	int C_1 = 0;
	for (int i = 0; i < count; i++) {
		for (int j = 0; j < count; j++) {
			if (map[i+y][j+x] == 1) {
				C_1 += 1;
			}
		}
	}

	if (C_1 == count* count) {// 모든칸이 1
		answer_b += 1;
	}
	else if(C_1==0) {// 모든칸이 0
		answer_w += 1;
	}
	else {
		cal(y, x, count / 2);
		cal(y, x + count / 2, count / 2);
		cal(y + count / 2, x , count / 2);
		cal(y + count / 2, x + count / 2, count / 2);
	}
}

 

 

끝!

 

재귀라는 개념만 안다면 풀수있는 쉬운문제였습니다!

 

 

 

ALL

#include <iostream>

using namespace std;

int N;
int answer_b = 0;
int answer_w = 0;

int map[129][129] = { 0 }; // 종이들

void cal(int y,int x, int count) {// 시작점, 한변 길이

	int C_1 = 0;
	for (int i = 0; i < count; i++) {
		for (int j = 0; j < count; j++) {
			if (map[i+y][j+x] == 1) {
				C_1 += 1;
			}
		}
	}

	if (C_1 == count* count) {// 모든칸이 1
		answer_b += 1;
	}
	else if(C_1==0) {// 모든칸이 0
		answer_w += 1;
	}
	else {
		cal(y, x, count / 2);
		cal(y, x + count / 2, count / 2);
		cal(y + count / 2, x , count / 2);
		cal(y + count / 2, x + count / 2, count / 2);
	}
}


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

	
	cin >> N;

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

	cal(0, 0 ,N);
	cout << answer_w << "\n";

	cout << answer_b << "\n";

	return 0;
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!