(백준 1780번 종이의 개수 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 2탄

후후 이번주도 1일 1알고리즘 가즈아~!

 

이전 포스팅은 여기에!↓

2024.01.07 - [알고리즘] - (백준 1992번 쿼드트리 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 1탄

(백준 1992번 쿼드트리 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 1탄

 

백준 1780번

https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

개인적으로 쿼드 트리랑 비슷해서 쉬울거라고 생각했는데...

놀랍게도 똑같은 실수를 했다😶

 

//1780 종이의 개수
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <utility>
int cnt1 = 0, cntm1 = 0, cnt0 = 0;

void Add(const int a) {
	if (a == -1) { cntm1++;  return; }
	if (a == 0) { cnt0++; return; }
	if (a == 1) { cnt1++;return; }
}
// 종이의 갯수를 세는 함수 , 분할정복, 3개의 sub문제로 나눔
void CountPaper(int**Arr, int N, int x, int y) {


	if (N == 1) { Add(Arr[x][y]); return; }
	std::vector<std::pair<int, int>> StartPoint = 
	{ {0,0}, {0, N / 3.}, {0, 2. * N / 3.},
	{N / 3., 0}, {N / 3., N / 3.}, {N / 3., 2. * N / 3.}, 
	{2. * N / 3., 0}, { 2. * N / 3., N / 3. }, { 2. * N / 3., 2. * N / 3. } };

	int temp = Arr[x][y];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (Arr[i+x][j+y] != temp) {
				if (N == 3) {
					for (int _i = 0; _i < 3; _i++) {
						for (int _j = 0; _j < 3; _j++) {
							CountPaper(Arr, N / 3, x+ _i, y+ _j);
						}
					}
				}
				else {
					for (int k = 0; k < 9; k++) {
						CountPaper(Arr, N / 3, x + StartPoint[k].first, y + StartPoint[k].second);
						//x, y 빼먹지마!!!!!
					}
				}
				return;
			}
		}
	}
	Add(temp);
	return;
}

int main() {
	int N;
	scanf("%d", &N);
	int** Arr = new int* [N];
	for (int i = 0; i < N; i++) {
		Arr[i] = new int[N]; {
			for (int j = 0; j < N; j++) scanf("%d", &Arr[i][j]);
		}
	}

	CountPaper(Arr, N, 0, 0);
	printf("%d\n%d\n%d", cntm1, cnt0, cnt1);
	for (int i = 0; i < N; i++) delete[]Arr[i];
	delete[]Arr;
	return 0;
}

 

생각보다 2차원을 분할하면 기준점이 헷갈린다. 특히 맨 처음에는 기준점을 (0,0)으로 두기 때문에 머릿속 머리디버깅에서는 문제가 없는 경우가 많고, 크기가 작은 예제를 돌리면 모두 정답처럼 보인다.

 

나 역시 반례를 찾지 못해서 고생하다가 결국 질문게시판을 뒤졌는데...! 개쩌는 반례를 누가 알려주셔서 그걸로 해결했다.

진짜 반례 못 찾으면 피눙물난다..

https://www.acmicpc.net/board/view/64880

글 읽기 - 반례좀 찾아주세요 ㅠㅠ

선생님 감사합니다.. 따봉 하나는 제꺼에요...⭐

27
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

안되시는 분들 이거 해보세요,, 답은 0 24 1 나와야 합니다...

 

진짜 집단지성으로 오늘 문제도 해결!!!

세상에 똑똑한 선생님들이 너무 많아서 공부하기 너무 좋은 세상이다

굴러가는게 너무 신나서 주석 처리 안하고 제출했더니 출력 초과..><