KOI 전국 2001 중1 - 색종이 만들기2(4진트리) > 문제은행 : 정보올림피아드&알고리즘



3560 : 색종이 만들기2(4진트리)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
178 회   
시도횟수
459 회   

문제

재우는 분할정복을 공부중이다.

그래서 1335:색종이 만들기 문제를 풀었다.

좀 더 공부하고 싶은 재우는​ 다음과 같은 문제를 생각해 보았다.

 

한 변의 길이가 2의 제곱수인 정사각형에 주어질 때,

주어진 정사각형에 포함된 숫자가 모두 0이면 0,

주어진 정사각형에 포함된 숫자가 모두 1이면 1 로 나타낸다.

그렇지 않고 주어진 정사각형에 포함된 숫자가 0, 1이 함께 있다면 

대문자 X로 그 영역을 나타내고 해당 영역을 4등분하여

재귀적으로 호출하여 같은 규칙을 적용한다.

4등분한 영역의 호출 순서는 좌상, 우상, 좌하, 우하 이다.

 

예를 들면 아래와 같은 정보가 주어지면

8

1 0 1 1 1 1 1 1

0 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1

0 0 0 0 1 1 1 1

1 1 0 0 0 0 0 0

1 1 0 0 0 0 0 0

0 0 1 1 0 0 0 0

0 0 1 1 0 0 0 0​ 

 

위의 규칙을 따르면 다음과 같은 결과가 만들어진다.

XXX10011001X10010​  


입력형식

첫 행에 한 변의 길이 N이 입력된다. 

(8 <= N <= 1024, N은 2의 제곱수) 다음 하나의 행에 정보가 입력된다.


출력형식

규칙에 따라 만들어진 문자열을 출력한다.


입력 예

8
1 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 1 1 0 0 0 0

출력 예

XXX10011001X10010​

데이타 만든사람 : comkiwer

Divide and Conquer

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP