백준 1780 - 종이의 개수(C++)

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

1780번: 종이의 개수

재귀로 풀 수 있는 문제였습니다.

문제 조건

출력 예시

원리는 https://junseok.tistory.com/117 참고해주세요!

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

 

 

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

#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[2200][2200];
int check[2200][2200];
int cnt_minus, cnt_zero, cnt_one;
bool fin = false;

void number_paper(int x, int cnt) {
	if (x == 0) {
		fin = true;
		return;
	}
	if (!fin) {
		for (int k1 = 0; k1 < cnt; k1++) {
			for (int k2 = 0; k2 < cnt; k2++) {
				int a = 0; // -1
				int b = 0; // 0
				int c = 0; // 1
				for (int i = 1 + x * k1; i <= x + x * k1; i++) {
					for (int j = 1 + x * k2; j <= x + x * k2; j++) {
						if (map[i][j] == -1 && check[i][j] == 0) a++;
						else if (map[i][j] == 0 && check[i][j] == 0) b++;
						else if (map[i][j] == 1 && check[i][j] == 0)c++;
					}
				}
				if (a == x * x || b == x * x || c == x * x) {
					for (int i = 1 + x * k1; i <= x + x * k1; i++) {
						for (int j = 1 + x * k2; j <= x + x * k2; j++) {
							check[i][j] = 1;
						}
					}
					if (a == x * x) cnt_minus++;
					else if (b == x * x) cnt_zero++;
					else cnt_one++;
				}
			}
		}
		number_paper(x / 3, cnt * 3);
	}
}

void solve() {
	number_paper(N, 1);
	cout << cnt_minus << "\n" << cnt_zero << "\n" << cnt_one;
}

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;
}

 

 

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