문제 링크 : https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수
www.acmicpc.net
C/C++ 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include <stdio.h>
int paper[2187][2187];
int count_minus = 0;
int count_zero = 0;
int count_one = 0;
void cut_paper(int x, int y, int n) {
int check = paper[x][y];
for (int i = x; i < x + n; i++) {
for (int j = y; j < y + n; j++) {
if (check != paper[i][j]) {
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
cut_paper(x + a * n / 3, y + b * n / 3, n / 3);
}
}
return;
}
}
}
if (check == -1) {
count_minus++;
}
else if (check == 0) {
count_zero++;
}
else {
count_one++;
}
}
int main() {
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%d", &paper[i][j]);
}
}
cut_paper(0, 0, N);
printf("%d\n%d\n%d\n", count_minus, count_zero, count_one);
return 0;
}
|
cs |
우선 paper를 전역변수로 사용했다. 이유는 재귀호출 하는 과정에서 paper를 인수로 넘기게되면 paper의 크기만큼의 메모리 공간이 계속해서 낭비될 것이기 때문이다.
코드의 핵심적인 부분은 9 ~ 18 Line이다. check는 나눠진 paper의 첫 번째(1행 1열) 요소를 저장하는 변수이다. paper내의 전체 요소 중 첫 번째 요소와 다른 요소가 하나라도 발견되면 cut_paper()를 재귀호출 하여 paper를 잘라야하기 때문에 조건문을 추가했다. 가장 어려웠던 부분은 15 Line의 cut_paper()를 재귀호출 하는 부분인데, 처음에 어떻게 9등분으로 자른 x,y값을 넘겨줘야 할지 감이 잘 오지 않았다. 고민하던 중 바깥 쪽 2중 for-loop의 안쪽에 다시 2중 for-loop를 사용하여 cut_paper()를 재귀호출하면 되겠다고 생각했다. 이렇게 하면 paper를 9개로 나누고, 나누어진 각각의 paper에 대해서 동일한 작업을 수행해줄 수 있다. 그리고 if의 조건에 걸려 재귀호출이 수행되면 count 변수들의 값을 증가시키지 않고 return하여 함수를 빠져나간다.
마지막으로는 check의 값을 확인해서 그 값에 따라 count_minus, count_zero, count_one 중 하나의 값을 1만큼 증가시킨다.
보통 주어진 문제를 2등분하는 D&C(분할정복) 문제를 자주 보는데, 이렇게 N등분하는 문제를 낼 수도 있구나라는 생각을 했다. 분할 정복은 언제봐도 참 마법같다는 생각이 든다.