알고리즘/코테 문제
[BOJ/백준 1780][C++] 종이의 개수
gyong
2023. 7. 20. 11:58
반응형
문제
https://www.acmicpc.net/problem/1780
문제 내용
아래 문제와 매우 유사한 문제이다.
[BOJ/백준 2630][C++] 색종이 만들기
문제 https://www.acmicpc.net/problem/2630 문제 내용 주어진 입력에서 색종이 개수를 구하는 문제이다. 색종이는 정사각형+같은 색이어야 하며, n*n 크기의 종이가 전부 같은 색이 아니면 가로 세로를 반
gyong0117.tistory.com
1780 종이의 개수 문제 역시 색종이의 개수를 구하는 문제이다.
차이는 2630번은 매번 n/2가 되지만 이 문제는 n/3을 해야 한다는 점, 종이의 종류가 다르다는 점이다.
문제 풀이
역시나 재귀를 통해 문제를 풀면 된다.
먼저 종이가 다 같은 수로 채워져 있는지를 체크하고, 그렇지 않으면 9등분하여 분할하여 각각에 대해 같은 과정을 거친다.
만약 다 같은 수로 채워져있으면 종이의 개수를 늘려주면 된다.
코드
#include <iostream>
using namespace std;
/**
* 1. 종이가 다 같은 수로 채워져 있는지 체크
* 2-1. 그렇지 않으면 분할
* 2-2. 다 같은 수이면 종이 개수 증가
*/
int arr[2288][2288]; // 3^7=2287
int n;
int cnt[3] = {0, 0, 0}; //-1, 0, 1 종이 개수
bool check(int stR, int stC, int len) {
int num = arr[stR][stC];
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (num != arr[stR + i][stC + j]) {
return false;
}
}
}
return true;
}
void checkAndDivide(int stR, int stC, int len) {
if (len == 1 || check(stR, stC, len)) { // 2-2. 다 같은 수일 때
cnt[arr[stR][stC] + 1]++;
return;
}
// 2-1. 다 같지 않으면 9등분으로 분할
len = len / 3;
checkAndDivide(stR, stC, len);
checkAndDivide(stR, stC + len, len);
checkAndDivide(stR, stC + 2 * len, len);
checkAndDivide(stR + len, stC, len);
checkAndDivide(stR + len, stC + len, len);
checkAndDivide(stR + len, stC + 2 * len, len);
checkAndDivide(stR + 2 * len, stC, len);
checkAndDivide(stR + 2 * len, stC + len, len);
checkAndDivide(stR + 2 * len, stC + 2 * len, len);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
checkAndDivide(0, 0, n);
cout << cnt[0] << "\n" << cnt[1] << "\n" << cnt[2];
}
반응형