1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.
www.acmicpc.net
학회 스터디 강의할 때 다룬 문제
우선 N*N 크기의 행렬로 표현되는 종이인지 확인한다.
만약 그렇다면 개수를 업데이트 해주고,
그렇지 않다면 종이를 아홉 등분하여 각각에 대해 또 다시 확인하면 된다.
풀이 자체가 문제를 세 줄로 요약한 거랑 다를 바가 없는데,
결국 이걸 어떻게 구현할 것인지가 관건인 것 같다.
#include <iostream>
using namespace std;
int arr[7000][7000]; // 3^7 = 6561. 배열의 크기가 크면 전역변수로 선언
int ans[3]; // -1, 0, 1이 적힌 종이 수 저장
void Solve(int y, int x, int size); // y행 x열부터 시작하는 size*size의 영역 확인
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> arr[i][j];
Solve(0, 0, n);
for (int i = 0; i < 3; i++) cout << ans[i] << '\n';
}
void Solve(int y, int x, int size) {
bool flag = true;
for (int i = y; i < y + size; i++) { //size*size 종이를 만들 수 있는지 확인
for (int j = x; j < x + size; j++) {
if (arr[i][j] != arr[y][x]) { //즉, 해당 범위에 있는 수들이 모두 같은 지 확인
flag = false;
break;
}
}
if (flag == false) {
break;
}
}
if (flag) {
ans[arr[y][x] + 1]++; //만약 이것이 하나의 종이라면 개수 업데이트, 분할 종료
return;
}
for (int i = y; i < y + size; i += size / 3) { //종이가 아니라면 이것을 9등분하여 각각 확인
for (int j = x; j < x + size; j += size / 3) {
Solve(i, j, size / 3);
}
}
}