C++ / 백준 / 1780 / 종이의 개수

문제

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

1780번: 종이의 개수

문제풀이

첫 줄부터 끝줄까지 최솟값과 최댓값을 구한다.

이전 최솟값, 이전 최댓값 변수를 만들어 이전에 돌린 max, min값들을 저장한다.

이전 최솟값, 이전 최댓값, 현재 최솟값, 최댓값이 다르면 종이를 9 분할한다.

다 같아 반복문을 다 돌면 해당 종이에 적힌 값의 개수를 1 늘린다.

 

		int prev_y = y;
		int prev_x = x;
		int max_value = 0;
		int min_value = 0;
		for (y; y < prev_y + size; ++y) {
			int prev_min = min_value;
			int prev_max = max_value;
			max_value = *max_element(paper[y].begin() + x, paper[y].begin() + x + size);
			min_value = *min_element(paper[y].begin() + x, paper[y].begin() + x + size);

			if (y != prev_y && (max_value != min_value || max_value != prev_max || min_value != prev_min)) {
				Divide(prev_y, prev_x, size / 3);
				Divide(prev_y + size / 3, prev_x, size / 3);
				Divide(prev_y + 2 * size / 3, prev_x, size / 3);

				Divide(prev_y, prev_x + size / 3, size / 3);
				Divide(prev_y + size / 3, prev_x + size / 3, size / 3);
				Divide(prev_y + 2 * size / 3, prev_x + size / 3, size / 3);

				Divide(prev_y, prev_x + 2 * size / 3, size / 3);
				Divide(prev_y + size / 3, prev_x + 2 * size / 3, size / 3);
				Divide(prev_y + 2 * size / 3, prev_x + 2 * size / 3, size / 3);
				break;
			}
		}

 

 

처음 for문을 돌릴 때는 이전 값이 존재할 수 없으므로 y!=prev_y (이때는 prev_y=y이다)가 아니고, 이전 최솟값, 이전 최댓값, 최솟값, 최댓값 중 하나라도 다른 값이 있으면 분할하는 코드.

y: 0 ~ 1/3 , 1/3 ~ 2/3, 2/3 ~ 3/3

x: 0 ~ 1/3 , 1/3 ~ 2/3, 2/3 ~ 3/3

해서 총 9 부분으로 나눈다.

한 번이라도 분할했으면 또 분할하면 안 되므로 breakm를 걸어 반복문을 종료한다.

 

		if (y == prev_y + size)
			cnt[paper[prev_y][prev_x] + 1]++;

cnt [0] = -1의 개수, cnt [1] = 0의 개수, cnt [2] = 1의 개수로 두었으므로 종이에 적힌 값 +1에 해당하는 곳의 값을 +1 한다.

 

	if (size == 1)
		cnt[paper[y][x] + 1]++;

3x3 배열을 9 분할하면 1칸짜리가 총 9개 생긴다. 더 분할할 수 없으므로 이 칸에 적힌 값 개수만큼 cnt배열 값을 늘려준다.

 

 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>>paper;
vector<int>cnt(3, 0);

void Divide(int y, int x,int size) {
	if (size == 1)
		cnt[paper[y][x] + 1]++;
	else {
		int prev_y = y;
		int prev_x = x;
		int max_value = 0;
		int min_value = 0;
		for (y; y < prev_y + size; ++y) {
			int prev_min = min_value;
			int prev_max = max_value;
			max_value = *max_element(paper[y].begin() + x, paper[y].begin() + x + size);
			min_value = *min_element(paper[y].begin() + x, paper[y].begin() + x + size);

			if (y != prev_y && (max_value != min_value || max_value != prev_max || min_value != prev_min)) {
				Divide(prev_y, prev_x, size / 3);
				Divide(prev_y + size / 3, prev_x, size / 3);
				Divide(prev_y + 2 * size / 3, prev_x, size / 3);

				Divide(prev_y, prev_x + size / 3, size / 3);
				Divide(prev_y + size / 3, prev_x + size / 3, size / 3);
				Divide(prev_y + 2 * size / 3, prev_x + size / 3, size / 3);

				Divide(prev_y, prev_x + 2 * size / 3, size / 3);
				Divide(prev_y + size / 3, prev_x + 2 * size / 3, size / 3);
				Divide(prev_y + 2 * size / 3, prev_x + 2 * size / 3, size / 3);
				break;
			}
		}
		if (y == prev_y + size)
			cnt[paper[prev_y][prev_x] + 1]++;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	paper = vector<vector<int>>(N, vector<int>(N, 0));
	int y = 0, x = 0;

	for (y = 0; y < N; ++y)
		for (x = 0; x < N; ++x)
			cin >> paper[y][x];

	Divide(0, 0, N);
	for (int idx = 0; idx < 3; idx++)
		cout << cnt[idx] << "\n";
}