[백준 / C언어] 1780번: 종이의 개수

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

1780번: 종이의 개수

난이도: solved.ac 실버 2

 

 

재귀를 이용하면 쉽게 풀 수 있다

 

먼저 시작점 arr[0][0]를 기준으로 find 라는 함수를 불렀다

 

이때 find 함수는 아래와 같다

 

int find(int x, int y, int N) {
	...
}

 

x와 y는 각각 arr의 행, 열을 의미하고 N은 종이의 크기를 나타낸다

 

find 함수 안에서는 base라는 변수로 arr[x][y]를 기준으로 잡아주고

 

한 칸씩 이동하며 base와 같은지 다른지 비교한다

 

이때 다른 수가 나오면 9등분하여 find를 다시 9번 호출하고

 

이때 diff라는 변수를 1로 바꿔주는데,

 

이는 다른 숫자를 발견해서 9등분 했으니 더 이상 비교 안 해도 된다는 걸 나타낸다

 

그리고 만약 모두 같은 수이면 answer라는 배열 내에 base 값의 개수를 하나 증가시켜 저장한다

 

answer[0]: -1의 개수

answer[1]: 0의 개수

answer[2]: 1의 개수

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 2187
 
int arr[MAX][MAX];
int answer[3];
void find(int x, int y, int N);
 
int main() {
	int N, i, j;
	scanf("%d", &N);
 
	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++)
			scanf("%d", &arr[i][j]);
 
	find(0, 0, N);
	printf("%d\n%d\n%d\n", answer[0], answer[1], answer[2]);
	return 0;
}
 
void find(int x, int y, int N) {
	int i, j, k, l;
	int base = arr[x][y];
	int diff = 0;
	/* 다른 수가 나와서 9등분 하게 되면 diff = 1이 됨 */
	for (i = x; i < x + N; i++) {
		for (j = y; j < y + N; j++) {
			/* 다른 수가 나오는 경우 */
			/* 한 번 9등분 하고나면 그 크기에서 더 이상 확인할 필요 없으므로 */
			if (arr[i][j] != base && diff == 0) {
				diff = 1;
				for (k = 0; k < 3; k++) {
					for (l = 0; l < 3; l++) {
						find(x + k * N / 3, y + l * N / 3, N / 3);
					}
				}
			}
		}
	}
	if (diff == 0)
		answer[base + 1]++;
}

 

(반례 모음)

 

3
1 1 1
1 -1 1
1 1 1


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