그림그리기1 > 문제은행



실전대비 Level8

1780 : 그림그리기1

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 3 회    시도횟수: 3 회   



진욱이는 컴퓨터 그림판(mspaint)을 자유 자재로 이용하여 예술 활동을 하는 화가다. 

그는 N x N개의 픽셀(컴퓨터 화면을 이루는 하나의 단위이자 점)에 그림을 그리고자 한다.

N은 2의 제곱수(1, 2, 4, 8, 16, etc...)다. 각 픽셀은 검은색이거나 하얀색이다. 진욱이는 다음과 같이 각 픽셀을 칠하고자 한다.

픽셀을 칠하는 방법은 조금 특이한데, 이는 재귀적인 과정을 거친다.

1. 그림이 한 개의 픽셀이면, 칠하고자 하는 색을 색칠한다.

2. 그렇지 않을 경우 그림을 동일한 크기의 4개의 정사각형으로 나누고 다음과 같이 칠한다.

4개의 정사각형 중 하나를 하얀색으로 칠한다.
칠해지지 않은 사각형중 하나를 골라서 검은색으로 칠한다.
칠해지지 않은 두개의 사각형을 다시 4개로 나누고 위의 과정을 반복한다.

 

진욱이는 위의 과정을 통해서 원하는 그림과 동일한 형태로 픽셀을 칠하고자 하는데, 

종종 동일하게 채우지 못하는 경우가 발생함을 알게 되었다. 

따라서 진욱이는 원하는 그림과 위의 과정을 통해 칠해진 그림에서 색상이 다른 픽셀의 수를 최소화 하고자 한다. 

최소가 되게끔 채우는 프로그램을 작성하여 진욱이를 도와주자.




입력의 첫 번째 줄에는 2의 제곱수의 형태인 정수 N(1≤N≤512)가 입력된다. 그 다음에는 그리고자 하는 그림에 대한 정보가 입력된다.

그림은 N개의 줄에는 N개의 0과 1로 이뤄진 문자로 입력되는데, 0은 해당 위치에 하얀색이고, 1의 경우는 검은색을 뜻한다.




위의 재귀적인 과정을 통해 그림을 그렸을 때 그리고자 하는 그림과의 색상이 다른 픽셀 수가 최소화 되었을 때의 값을 출력한다.



4
0001
0001
0011
1110
1



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.