개요

[링크]백준 1780번: 종이의 개수

• 입력
  첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

• 출력
  첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

접근 방식

각 재귀에서 모든 원소가 같은 값인지 체크하고,
하나라도 달라지면 9등분해서 9개의 재귀를 호출하는 방식으로
생각을 하였다.

고민했던 부분은 모든 원소가 같은 값인지 체크하는 부분이였는 데,
첫 값을 저장하고 그 값과 모든 원소를 비교하는 방식으로 풀었다.

코드

#include<iostream>
#include<vector>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);

using namespace std;
vector<vector<int>> v;
vector<int> v2;
int minusOne=0, zero=0, one = 0;
void input(int& amount){
	int temp=0;
	cin >> amount;
	for (int i = 0; i < amount; i++) {
		v2.clear();
		for (int j = 0; j < amount; j++) {
			cin >> temp;
			v2.push_back(temp);
		}
		v.push_back(v2);

	}


}

void solution(int x, int y, int length) {
	int temp = v[x][y];								//각 단계에서 첫값을 넣어준 후 이값과 다르면 같은 숫자로 이뤄지지 않음 판단

	if (length == 0) return;						//3으로 나눴을 때 길이 0이면 return
	for (int i = x; i < x+length; i++) {				//x부터 length가 아니라 x부터 x+length로 해야지
		for (int j = y; j < y+length; j++) {
			if (v[i][j] != temp) {					//만약 다르면 전체가 같은걸로 이뤄지지 않았으므로 9개 재귀
				solution(x, y, length / 3);
				solution(x, y + length / 3, length / 3);
				solution(x, y + 2 * length / 3, length / 3);
				solution(x + length / 3, y, length / 3);
				solution(x + length / 3, y + length / 3, length / 3);
				solution(x + length / 3, y + 2 * length / 3, length / 3);
				solution(x + 2 * length / 3, y, length / 3);
				solution(x + 2 * length / 3, y + length / 3, length / 3);
				solution(x + 2 * length / 3, y + 2 * length / 3, length / 3);
				return;								//똑같은거로 이뤄져있는데 빠져나와서 밑에 답에 영향주는 식으로 가면 안돼!
			}
		}
	}												//빠져나왔다면 같은 것으로 이뤄져있으므로
	if (temp == 0) {								//0으로 이뤄져 있다면 zero++
		zero++;
		return;
	}
	else if (temp == 1) {							//1로 이뤄져있다면 one++
		one++;
		return;
	}
	else											//-1로 이뤄져있다면 minusOne++
	{
		minusOne++;
		return;
	}

}

int main() {
	FAST											//연산 빠르게 해준다. 실제로 4배 차이가 남 
	int amount;
	input(amount);
	solution(0, 0, amount);
	cout << minusOne<<'\n' << zero<<'\n' << one;
}

문풀후생

처음에 재귀에서 반복문을 돌릴 때,
아무생각없이 int i=x; i<length;i++ 이렇게 적었다가
오류나서 발견했다.. i가 x+length까지 여야하는데,,
덤벙댔다.

또한, N의 범위가 1 ≤ N ≤ 3^7이라 그런지
FAST로 define해준 식을 사용하면
백준 기준으로 시간이

3배가 차이난다...