알고리즘/분할정복 & 재귀 & 백트래킹
[백준] 1780 종이의 개수
HJ39
2023. 5. 4. 23:43
종이의 개수 문제는 이전에 블로그에 올렸던 색종이 만들기 문제와 완전 똑같다.
#include <bits/stdc++.h>
#define MAXARANGE 2200
using namespace std;
vector<vector<int>> input1780(MAXARANGE,vector<int>(MAXARANGE,0));
int minusOneCount = 0;
int oneCount = 0;
int zeroCount = 0;
void recursive1780(int N, int x, int y){
if(N==1){
if(input1780[x][y] == 1)
oneCount++;
else if(input1780[x][y] == 0)
zeroCount++;
else if(input1780[x][y] == -1)
minusOneCount++;
return;
}
bool minusOneCheck = false;
bool oneCheck = false;
bool zeroCheck = false;
for(int i=x;i<x+N;i++){
for(int j=y;j<y+N;j++){
if(input1780[i][j] != 1)
oneCheck = true;
if(input1780[i][j] != 0)
zeroCheck = true;
if(input1780[i][j] != -1)
minusOneCheck = true;
}
}
if(!minusOneCheck){
minusOneCount++;
return;
}
if(!oneCheck){
oneCount++;
return;
}
if(!zeroCheck){
zeroCount++;
return;
}
int divide[] = {0,N/3,(N*2)/3};
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
recursive1780(N/3, x+divide[i], y+divide[j]);
}
}
}
void paperCount1780(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N; cin>>N;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
cin>>input1780[i][j];
recursive1780(N, 1, 1);
cout<<minusOneCount<<"\n";
cout<<zeroCount<<"\n";
cout<<oneCount<<"\n";
}