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

문제 링크입니다. https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

재귀를 이용하는 문제였습니다.

문제 조건

출력 예시

N의 값에 따라서 탐색해야할 수가 달라집니다.

N이 8일 경우 -> (8 * 8) 1번 확인, (4 * 4) 4번 확인, (2 * 2) 16번 확인, (1 * 1) 64번 확인

이와 같이 N/2가 될때마다, 확인해야할 사각형의 수가 4배가 증가합니다.

 

따라서 재귀 함수에서 N값과 Cnt를 통해서 탐색 범위를 늘려줘야합니다.

이때 만들수 있는 X*X 크기의 사각형을 잘랐을 경우, 다시 확인하면 안됨으로 check배열을 통해서 확인해줍니다. 

 

 

for (int k = 0; k < cnt; k++) {
		for (int k1 = 0; k1 < cnt; k1++) {
			int num_1 = 0;
			int num_0 = 0;
			for (int i = 1 + x * k; i <= x + x * k; i++) {
				for (int j = 1 + x * k1; j <= x + x * k1; j++) {
					if (map[i][j] == 0 && check[i][j] == 0) num_0++;
					else if(map[i][j] == 1 && check[i][j] == 0)num_1++;
				}
			}
			if (num_1 == x * x || num_0 == x * x) {
				if (num_1 == x * x) {
					for (int i = 1 + x * k; i <= x + x * k; i++) {
						for (int j = 1 + x * k1; j <= x + x * k1; j++) {
							check[i][j] = 1;
						}
					}
					cnt_1++;
                  }
				else {
					for (int i = 1 + x * k; i <= x + x * k; i++) {
						for (int j = 1 + x * k1; j <= x + x * k1; j++) {
							check[i][j] = 1;
						}
					}
					cnt_0++;
				}
			}
		}
	}

cnt값에 따라서 이중 for문을 반복해,  x*x 크기의 사각형을 탐색해줬습니다.

예를 들어,  x = 4이고, cnt = 2일 때,

1. i = (1 + x * cnt ~ x + x * cnt) -> (0 ~ 4),  j도 똑같이 (0 ~ 4)

2. i = (0 ~ 4) , j = (1 + x * cnt ~ x + x * cnt) -> (5 ~ 8)

3. i = (5 ~ 8) , j = (1 ~ 4)

4. i = (5 ~ 8) , j = (5 ~ 8)

이와 같은 방법으로 계속 반복합니다. 

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N;
int map[129][129];
int check[129][129];
int cnt_0, cnt_1;
bool fin = false;

void find_square(int x, int cnt) {
	if (x == 0) {
		fin = true;
		return;
	}
	if (!fin) {
		for (int k = 0; k < cnt; k++) {
			for (int k1 = 0; k1 < cnt; k1++) {
				int num_1 = 0;
				int num_0 = 0;
				for (int i = 1 + x * k; i <= x + x * k; i++) {
					for (int j = 1 + x * k1; j <= x + x * k1; j++) {
						if (map[i][j] == 0 && check[i][j] == 0) num_0++;
						else if(map[i][j] == 1 && check[i][j] == 0)num_1++;
					}
				}
				if (num_1 == x * x || num_0 == x * x) {
					if (num_1 == x * x) {
						for (int i = 1 + x * k; i <= x + x * k; i++) {
							for (int j = 1 + x * k1; j <= x + x * k1; j++) {
								check[i][j] = 1;
							}
						}
						cnt_1++;
					}
					else {
						for (int i = 1 + x * k; i <= x + x * k; i++) {
							for (int j = 1 + x * k1; j <= x + x * k1; j++) {
								check[i][j] = 1;
							}
						}
						cnt_0++;
					}
				}
			}
		}
		find_square(x / 2, cnt * 2);
	}
}

void solve() {
	find_square(N,1);
	cout << cnt_0 << "\n" << cnt_1;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!