반응형
728x170
이것 또한
분할 정복
Z자로 진행하는 방식이다.
더 어려워졌다면 9개로 늘어난거..?
시간도 많다
https://www.acmicpc.net/problem/1780
#맞은 풀이
틀린 부분에 대해서는 내가 주석을 좀 달아놨다.
#include<iostream>
#include<vector>
#define X first
#define Y second
using namespace std;
int N;
int map[2200][2200];
int mm = 0;
int zz = 0;
int pp = 0;
void func(int N, int a, int b) {
if (N == 1) {
int std = map[a][b];
if (std == 1) {
pp++;
}
else if (std == 0) {
zz++;
}
else {
mm++;
}
return; // N=1이면 여기까지만 진행
}
//9개의 좌표
vector<pair<int, int>> vec;
vec.push_back({ a,b });
vec.push_back({ a,b + N/3 });
vec.push_back({ a,b + 2*N/3 });
vec.push_back({ a + N / 3,b });
vec.push_back({ a + N / 3,b + N / 3 });
vec.push_back({ a + N / 3,b + 2 * N / 3 });
vec.push_back({ a + 2 * N / 3,b });
vec.push_back({ a + 2 * N / 3,b + N / 3 });
vec.push_back({ a + 2 * N / 3,b + 2 * N / 3 });
int check = map[a][b]; // 기준
int diff = map[a][b]; // 비교
//전체를 체크해서 아니면 9개로 가름
//0부터 시작해야함...또틀림
for (int i = 0; i<N; i++) {
if (check != diff)break; //2
for (int j = 0; j<N; j++) {
//만약 이 종이에 다른 것이 섞여있다면
//이 for문은 소용없음 2중 루프이므로 break포인트 2개
//9개로 나눔.
if (check != map[a+i][b+j]) {
diff = map[a+i][b+j];
func(N / 3, vec[0].X, vec[0].Y);
func(N / 3, vec[1].X, vec[1].Y);
func(N / 3, vec[2].X, vec[2].Y);
func(N / 3, vec[3].X, vec[3].Y);
func(N / 3, vec[4].X, vec[4].Y);
func(N / 3, vec[5].X, vec[5].Y);
func(N / 3, vec[6].X, vec[6].Y);
func(N / 3, vec[7].X, vec[7].Y);
func(N / 3, vec[8].X, vec[8].Y);
break; // 1
}
}
}
//다르면 종료
if (diff != check) {
return;
}
// 끝까지 같으면
else {
if (check == diff) {
if (check == 1) {
pp++;
}
else if (check == 0) {
zz++;
}
else {
mm++;
}
}
}
}
int main() {
cin >> N;
//N*N개 입력, 인덱스 1부터 씀.
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> map[i][j];
}
}
func(N, 1, 1);
cout << mm << "\n" << zz << '\n' << pp;
}
여기서 포인트는
전체를 먼저 검사하고 그것이 안되면
9가지로 나눈다는 것.(좌표넣을 순서는 어떤 식인지 관찰해서 얻어내자) -> 여기선 상관없었음
가장 작게 나눴을 때 종료조건을 만들어줘야 한다는 것.
이와 비슷한 문제가 또 있다.
[문제풀이(Problem Solving)] - 백준, BOJ, 1992번 C++ [CPP]
[문제풀이(Problem Solving)] - 백준, BOJ, 2630번 C++ [CPP]
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 1620번 C++ [CPP] (0) | 2021.06.14 |
---|---|
백준, BOJ, 1074번 C++ [CPP] (0) | 2021.06.14 |
백준, BOJ, 1992번 C++ [CPP] (0) | 2021.06.14 |
백준, BOJ, 2630번 C++ [CPP] (0) | 2021.06.14 |
백준, BOJ, 3036번 C++ [CPP] (0) | 2021.06.11 |