2002년 가을학기 문제해결기법 - 문제 6

L형 다각형 분할

한국대학교 양 문원, 김 재선 학생은 대학생 프로그래밍 대회에 참가하기 위하여 준비하고 있다. 오늘도 관련 문제를 찾고 있었는데, 우연히 다른 팀 학생에게 다음과 같은 문제를 듣게 되었다.

가로와 세로의 길이가 모두 인 정사각형 색종이가 주어져 있을 때, 이것을 아래와 같이 크기와 모양이 정해진 최대 개수의 L형 다각형으로 분할하는 것이다. 여기서 고려하고 있는 L형 다각형은 길이 1인 정사각형 3개를 붙여서 만들 수 있는 L자 모양의 다각형을 말한다.

가로와 세로의 길이가 4인 색종이가 주어진 경우는 아래와 같이 5개의 L형 다각형으로 분할 할 수 있다. 그리고 남은 조각의 면적이 L형 다각형의 면적보다 작으므로 5개가 최대가 됨을 알 수 있다.

1	1	2	2
1	4	4	2
3		4	5
3	3	5	5

가로, 세로의 길이가 모두 인 정사각형 색종이가 주어질 때, 이 색종이를 분할하여 얻을 수 있는 L형 다각형의 최대 개수와 어떻게 분할하는지를 출력하는 프로그램을 작성하시오. 여기서 은 2의 거듭제곱 수, 즉 이라고 가정한다 (는 양의 정수). 남은 조각은 길이 1인 정사각형들이거나 혹은 그것들을 붙여서 만들 수 있는 다각형들이다.

프로그램 이름과 설명 파일 이름은 각각 Lshape.xxx, Lshape.yyy라고 하고 실행 파일 이름은 Lshape.exe로 한다. 프로그램의 실행 시간은 3초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫 줄에 정사각형의 가로 길이 이 입력된다. 은 1024 이하인 2의 거듭제곱 수이다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 L형 다각형의 최대 개수를 출력한다. 둘째 줄부터 개의 줄에 L형 다각형으로 분할한 모양을 아래 예와 같이 출력한다. 즉, 각 L형 다각형에 대해서 1부터 차례로 번호를 붙이고, 그 L형 다각형이 포함하는 길이 1인 정사각형에 L형 다각형의 번호를 출력한다. 분할하고 남은 조각에 대해서는 모두 0을 출력한다. 각 줄에 개의 정수를 출력하여야 하며, 이들 사이에는 공백이 있다.

입력과 출력의 예

INPUT.TXT

4

OUTPUT.TXT

5

1 1 2 2

1 4 4 2

3 0 4 5

3 3 5 5