백준 1992

문제 분석

 

언제 괄호를 열고 닫아야 하는지? 

 

1. 똑같은 영상으로 이루어지지 않은 경우

• 4등분을 하기 전에 괄호를 한 번 열어주고 4등분한 재귀함수가 모두 끝난 이후 괄호를 닫아줌

 

 

주어진 영상이 모두 똑같은 수로만 되어있으면 괄호로 묶을 필요가 없음 
--> 이 말을 이해하지 못해서 똑같은 수로 되어 있는 경우도 괄호로 묶어버림 

 

코드

#include<iostream>	
using namespace std;

int board[65][65];

bool valSameCk(int n, int x, int y) {
	for (int i = x; i < x + n; i++) {
		for (int j = y; j < y + n; j++) {
			if (board[x][y] != board[i][j]) return false;
		}
	}
	return true;
}

void func(int n, int x, int y) {
	
	if (valSameCk(n, x, y)) {
		cout << board[x][y];
	}
	else {
		cout << '(';
		int half = n / 2;
		// 4등분을 하고 각 지점의 시작위치를 잡아주기 
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				func(half, x + half * i, y + half * j);
			}
		}
		cout << ')';
	}

}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	// 1.입력
	int N;
	cin >> N; // 2의 n승 형태

	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < N; j++) {
			board[i][j] = str[j] - '0'; // 문자 1 아스키 코드 값 49 - 문자 0 아스키 코드 값 48 = 1이 나오게 됨
		}	
	}

	// 2.로직	
	func(N, 0, 0);		

	return 0;
}

 

cin은 스페이스, 개행 단위로 값을 입력받기 때문에 문제가 공백없이 주어져서 한줄씩 문자열로 받아서 각 배열에 정수로 변환해서 집어넣음