문제 링크
풀이
분할 정복
문제
- 먼저 모두 같은지 확인하는
check
함수로 해당 영역이 모두 같은 숫자라면true
, 아니라면false
를 return한다.- 영역이 모두 같으면
answer
에 해당 숫자를 추가한다.
- 영역이 모두 같으면
- 아니라면 영역을 나눠주는데,
(
괄호를 먼저 추가하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 재귀호출한다. 이 때size
는 반으로 줄여준다. - 모든 호출이 끝나면
answer
에)
괄호를 추가해준다.
코드
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string answer = "";
bool check(vector<vector<char>> &v, int size, int y, int x)
{
char c = v[y][x];
for (int i = y; i < y + size; i++)
{
for (int j = x; j < x + size; j++)
{
if (c != v[i][j]) return false;
}
}
return true;
}
void func(vector<vector<char>> &v, int size, int y, int x)
{
if (check(v, size, y, x))
{
answer += v[y][x];
}
else
{
answer += '(';
func(v, size / 2, y, x); // 왼쪽 위
func(v, size / 2, y, x + size / 2); // 오른쪽 위
func(v, size / 2, y + size / 2, x); // 왼쪽 아래
func(v, size / 2, y + size / 2, x + size / 2); // 오른쪽 아래
answer += ')';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector<char>> v(n, vector<char>(n));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> v[i][j];
}
}
func(v, n, 0, 0);
cout << answer << endl;
return 0;
}
문제 링크
풀이
분할 정복
문제
- 먼저 모두 같은지 확인하는
check
함수로 해당 영역이 모두 같은 숫자라면true
, 아니라면false
를 return한다.- 영역이 모두 같으면
answer
에 해당 숫자를 추가한다.
- 영역이 모두 같으면
- 아니라면 영역을 나눠주는데,
(
괄호를 먼저 추가하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 재귀호출한다. 이 때size
는 반으로 줄여준다. - 모든 호출이 끝나면
answer
에)
괄호를 추가해준다.
코드
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string answer = "";
bool check(vector<vector<char>> &v, int size, int y, int x)
{
char c = v[y][x];
for (int i = y; i < y + size; i++)
{
for (int j = x; j < x + size; j++)
{
if (c != v[i][j]) return false;
}
}
return true;
}
void func(vector<vector<char>> &v, int size, int y, int x)
{
if (check(v, size, y, x))
{
answer += v[y][x];
}
else
{
answer += '(';
func(v, size / 2, y, x); // 왼쪽 위
func(v, size / 2, y, x + size / 2); // 오른쪽 위
func(v, size / 2, y + size / 2, x); // 왼쪽 아래
func(v, size / 2, y + size / 2, x + size / 2); // 오른쪽 아래
answer += ')';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector<char>> v(n, vector<char>(n));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> v[i][j];
}
}
func(v, n, 0, 0);
cout << answer << endl;
return 0;
}