문제 링크 : https://www.acmicpc.net/problem/1780
요약
-1, 0, 1로 이루어진 N x N의 행렬이 있을 때 전체 영역이 모두 같은 값이라면 한 장만 사용해도 되고,
그게 아니라면 가로 3, 세로 3 영역으로 9등분하여 각 영역이 모두 같은 값으로 이루어질 때까지 나누었을 때 -1, 0, 1로만 채워진 종이의 각각의 개수를 구하는 문제.
풀이
전형적인 분할정복 문제!! 부분 행렬의 전부를 탐색했을 때 모두 같은 값이라면 한 장만 사용하도록 기저를 잡고 그게 아니라면 재귀 함수를 이용해서 9등분하여 조건에 해당하는지 확인하고 각 영역의 답을 모두 합병해준다.
코드
#include<iostream>
using namespace std;
int n, arr[2200][2200];
int ans[3];
void sol(int d, int r, int cnt) {
int num = arr[d][r];
int chk = -1;
for (int i = d; i < d + cnt; i++) {
for (int j = r; j < r + cnt; j++) {
if (num != arr[i][j]) {
chk = 1;
}
}
}
if (chk == -1) {
ans[num + 1]++;
return;
}
int div = cnt / 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
sol(d + div * i, r + div * j, div);
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
sol(0, 0, n);
for (int i = 0; i < 3; i++)
cout << ans[i]<<"\n";
}
'BOJ' 카테고리의 다른 글
BOJ 9012 괄호 (0) | 2022.03.24 |
---|---|
BOJ 1992 쿼드트리 (1) | 2022.03.17 |
BOJ 1725 히스토그램 (0) | 2022.03.14 |
BOJ 2104 부분배열 고르기 (2) | 2022.03.12 |
BOJ 1629 곱셈 (0) | 2022.03.12 |
댓글