[백준] 1780번 종이의 개수
in Algorithms on BOJ
Divide & Conquer
문제설명
문제
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.
만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
- (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
- 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1≤N≤3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.
출력
첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.
접근
전형적인 Divide & Conquer(분할정복) 문제이다. 입력된 배열을 조건을 확인하며 아홉 부분으로 나누어 재귀적으로 해결하면 된다.
코드
#include <iostream>
#define MAX_NUM 2200
using namespace std;
int arr[MAX_NUM][MAX_NUM];
int ans[3];
bool checkArray(int a, int b, int term){
int num = arr[a][b];
for(int i=0; i<term; i++){
for(int j=0; j<term; j++){
if(num != arr[a+i][b+j])
return false;
}
}
return true;
}
void divideNconquer(int a, int b, int term){
bool isAllSame = checkArray(a, b, term);
if(!isAllSame){
int new_term = term/3;
for(int i=0; i<3; i++){
int new_a = a + i*new_term;
for(int j=0; j<3; j++){
int new_b = b + j*new_term;
divideNconquer(new_a, new_b, new_term);
}
}
}
else{
int num = arr[a][b];
ans[num+1]++;
}
}
int main(){
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
int n;
cin >> n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin >> arr[i][j];
}
}
divideNconquer(0,0,n);
for(auto x : ans)
cout << x << '\n';
}
참고
이 글이 도움이 되셨다면 추천 클릭을 부탁드립니다 :)
