이런 문제다.
그렇다면, 분할정복 기법을 사용한다. 어차피 1*1 2*2 4*4 .... 이런 것들만 있으니까 안되면 자르고 되면 넣고 하면 된다. 단순한 문제,
#include <iostream>
#include <vector>
using namespace std;
int cutting(vector<int> &ans, vector<vector<int>> paper, int size);
int check(vector<vector<int>> paper, int size);
int main()
{
int size;
cin >> size;
int cnt = 0;
vector<vector<int>> arr(size+1);
vector<int> ans(3);
ans[0] = ans[1] = 0;
for (int i = 0; i < size; i++)
{
arr[i] = vector<int>(size + 1);
for (int j = 0; j < size; j++)
{
cin >> arr[i][j];
cnt += arr[i][j];
}
}
if (cnt == 0 || cnt == size * size)
{
if (cnt == 0)
{
cout << 1 << endl << 0;
}
else
{
cout << 0 << endl << 1;
}
}
else
{
cutting(ans, arr, size);
}
for (int i = 0; i < 2; i++)
cout << ans[i] << endl;
return 0;
}
int cutting(vector<int>& ans, vector<vector<int>> paper, int size)
{
int tmp = check(paper, size);
if (tmp != 2)
{
ans[tmp]++;
return 0;
}
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];
}
}
cutting(ans, p1, size / 2);
cutting(ans, p2, size / 2);
cutting(ans, p3, size / 2);
cutting(ans, p4, size / 2);
}
return 0;
}
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 16916 부분 문자열 (0) | 2021.01.09 |
---|---|
BOJ 1992 쿼드트리 (0) | 2021.01.08 |
코테 준비반 2일차 (프로그래머스 고득점 KIT 완전 탐색 (모의고사, 소수 찾기, 카펫)) (0) | 2020.08.31 |
오늘은 프로그래머스를 했다.(고득점 KIT 정렬) (0) | 2020.08.30 |