문제
아래와 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 0으로 칠해져 있거나 1로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 0 또는 1로 칠해진 색종이를 만들려고 한다.
11000011
11000011
00001100
00001100
10001111
01001111
00111111
00111111
전체 종이의 크기가 N×N(N=2^k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.
전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 0 또는 모두 1으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.
입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(0 또는 1)이 주어질 때 잘린 조각들 중 0으로 칠해진 색종이의 수와 1로 칠해진 색종이의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.
각 숫자 사이에는 빈칸이 하나씩 있다.
출력
첫째 줄에는 잘라진 색종이들 중 0으로 칠해진 색종이의 수를 출력하고, 두 번째 줄에는 잘린 색종이들 중 1로 칠해진 색종이의 수를 출력하라.
힌트
예제 입력
8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1
예제 출력
9
7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | #include<iostream>#include<fstream>using namespace std; int N;int A[128][128]; struct color{ int zero; int one; color& operator + (color c) { one += c.one; zero += c.zero; return *this; }}; color devide(int r, int c, int size) { color res = { 0,0 }; int one = 0; int zero = 0; bool isSameColor = true; for (int i = r; i < r + size; i++) { for (int j = c; j < c + size; j++) { if (A[i][j] == 1) { one += 1; } else { zero += 1; } if (one > 0 && zero >0) { //0과 1이 섞여 있다면 isSameColor = false; break; } } } if (isSameColor) { if (one > 0) { res = { 1,0 }; } else { res = { 0,1 }; } } else { // 4등분으로 쪼갬 int half = size / 2; res = res + devide(r, c, half); res = res + devide(r+ half, c, half); res = res + devide(r, c+ half, half); res = res + devide(r+ half, c+ half, half); } return res;} int main() { //ifstream cin("input.txt"); cin >> N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> A[i][j]; } } color res = devide(0, 0, N); //0의 개수 cout << res.one << endl; cout << res.zero << endl; //system("pause"); return 0;} |
