[ 문제 ] : https://www.acmicpc.net/problem/2630
2630번: 색종이 만들기
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.
www.acmicpc.net
[ 문제 접근 ]
바로 전에 풀었던 종이의 개수와 똑같은 문제이다.
다른점은 9 등분이 아니라 4 등분 이라는 점.
백준 1780 풀이 :: https://forward-movement.tistory.com/66?category=976225
[ 최종 코드 ]
#include<iostream>
#include<vector>
#include<string>
using std::cin; using std::cout;
using std::vector;
int n;
int graph[129][129];
bool is_same = true;
int arr[2];
void solve(int n, int a, int b) {
if (n == 1) { // base case
arr[graph[a][b]]++;
return;
}
int pivot = graph[a][b];
bool is_same = true;
for (int i = a; i < a+n; i++) {
for (int j = b; j < b+n; j++) {
if (pivot != graph[i][j]) {
is_same = false;
break;
}
}
if (!is_same)break;
}
if (!is_same) {
solve(n / 2, a, b);
solve(n / 2, a + n/2, b);
solve(n / 2, a, b + n / 2);
solve(n / 2, a + n / 2, b + n / 2);
}
else {
arr[graph[a][b]]++;
}
return;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> graph[i][j];
}
}
solve(n, 0, 0);
cout << arr[0] << '\n' << arr[1];
return 0;
}
'PS > BaekJoon' 카테고리의 다른 글
[9663] N-Queen - 백트랙킹 ★★☆☆ / 복습 ○ (0) | 2021.12.10 |
---|---|
[2252] 쿼드트리 - 재귀/분할정복 ★★☆☆ / 복습 ○ (0) | 2021.12.02 |
[1780] 종이의 개수 - 재귀 / 분할 정복 ★★☆☆ / 복습 ○ (0) | 2021.12.02 |
[10799] 쇠막대기 - 스택 ★★☆☆ / 복습 ○ (0) | 2021.11.30 |
[1504] 특정한 최단 경로 - 최단경로 ★★★☆ / 복습 ○ (0) | 2021.11.28 |