문제
풀이
분할정복을 이용한 문제이다. NxN에서 모든 원소의 합이 0이면 0을 출력, NxN이면 모두 1이라는 소리이므로 1을 출력한다. 그렇지 않다면, x, y 좌표를 기억하며, N/2만큼 x, y좌표 각각 떨어진 4개로 분할하여 함수를 호출한다. ( )의 위치는 왼쪽 위가 나오기 전, 오른쪽 아래가 나온 이후로 각각 배치하여 문제의 정답을 도출해낸다.
소스 코드
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
#include <iostream>
#include <string.h>
using namespace std;
int map[64][64];
void screen(int a, int x, int y){
int temp = 0;
for(int i = 0; i<a; i++){
for(int j = 0; j<a; j++){
temp = temp + map[x+i][y+j];
}
}
if(temp == 0){
printf("0");
}
else if(temp == a*a){
printf("1");
}
else{
printf("(");
screen(a/2, x+0, y+0);
screen(a/2, x+0, y+a/2);
screen(a/2, x+a/2, y+0);
screen(a/2, x+a/2, y+a/2);
printf(")");
}
}
int main(){
int N;
scanf("%d", &N);
for(int i = 0; i<N; i++){
string num;
cin >> num;
for(int j = 0; j<N; j++){
map[i][j] = (num[j]-'0');
}
}
screen(N, 0, 0);
}
