https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수
www.acmicpc.net
난이도: 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