색종이 문제랑 똑같은데 왜 랭크는 높은지 1도 이해할 수 없는 문제다. 똑같이 풀었다. 아니 사실 다른 점이 있긴 한데, 그냥... 내가 자른 것이 내 생각대로 잘리진 않아서 코드 한 60번째 줄 보면 2랑 3이랑 바뀌어있을거다. 그거다. 확인해보고 싶으면 출력하면 된다.
#include <iostream>
#include <vector>
using namespace std;
int check(vector<vector<int>> paper, int size);
string quadTree(vector<vector<int>> paper, int size);
int main()
{
int size;
cin >> size;
vector<vector<int>> paper(size);
for (int i = 0; i < size; i++)
{
paper[i] = vector<int>(size);
string tmp;
cin >> tmp;
for (int j = 0; j < size; j++)
{
paper[i][j] = tmp[j] - 48;
}
}
cout << quadTree(paper, size) ;
return 0;
}
string quadTree(vector<vector<int>> paper, int size)
{
int tmp = check(paper, size);
if (tmp != 2)
{
if (tmp == 0)
{
return "0";
}
else
{
return "1";
}
}
else
{
vector<vector<int>> p1(size / 2), p2(size / 2), p3(size / 2), p4(size / 2);
for (int i = 0; i < size / 2; i++)
{
p1[i] = vector<int>(size / 2);
p2[i] = vector<int>(size / 2);
p3[i] = vector<int>(size / 2);
p4[i] = vector<int>(size / 2);
for (int j = 0; j < size / 2; j++)
{
p1[i][j] = paper[i][j];
p2[i][j] = paper[i + size / 2][j];
p3[i][j] = paper[i][j + size / 2];
p4[i][j] = paper[i + size / 2][j + size / 2];
}
}
string a1 = quadTree(p1, size / 2);
string a3 = quadTree(p2, size / 2);
string a2 = quadTree(p3, size / 2);
string a4 = quadTree(p4, size / 2);
return "(" + a1 + a2 + a3 + a4 + ")";
}
}
int check(vector<vector<int>> paper, int size)
{
int cnt = 0;
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
cnt += paper[i][j];
}
if (cnt == 0)
{
return 0;
}
else if (cnt == size * size)
{
return 1;
}
else
return 2;
}
'vidigummy KAU > 알고리즘 공부(백준!)' 카테고리의 다른 글
BOJ 1780 종이의 개수 (0) | 2021.01.10 |
---|---|
BOJ 16916 부분 문자열 (0) | 2021.01.09 |
BOJ 2630 색종이 만들기 (0) | 2021.01.08 |
코테 준비반 2일차 (프로그래머스 고득점 KIT 완전 탐색 (모의고사, 소수 찾기, 카펫)) (0) | 2020.08.31 |