레이팅 미적용전 세계 미술 평론가들은 최근에서야 위대한 소 화가 피카우소(Picowso)의 창조적 천재성을 알아보기 시작했다.
피카우소는 매우 독특한 방식으로 그림을 그린다. 그녀는 \(N \times N\) 크기의 빈 캔버스에서 시작하는데, 이는 \(N \times N\) 격자의 0들로 표현되며 0은 캔버스의 빈 칸을 나타낸다. 그런 다음 캔버스에 \(N^2\)개의 직사각형을 그리는데, 각각은 \(N^2\)가지 색(편의상 \(1 \ldots N^2\)번) 중 하나로 칠한다. 예를 들어 먼저 색 2로 직사각형을 칠하면 다음의 중간 캔버스가 된다.
2 2 2 0
2 2 2 0
2 2 2 0
0 0 0 0
그다음 색 7로 직사각형을 칠할 수 있다.
2 2 2 0
2 7 7 7
2 7 7 7
0 0 0 0
그리고 색 3으로 작은 직사각형을 칠할 수 있다.
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0
각 직사각형의 변은 캔버스의 변과 평행하며, 직사각형은 캔버스 전체만큼 클 수도 있고 한 칸만큼 작을 수도 있다. \(1 \ldots N^2\)의 각 색은 정확히 한 번씩 사용되지만, 나중에 칠한 색이 먼저 칠한 색을 완전히 덮어 버릴 수도 있다.
안타깝게도 피카우소가 너무 유명해진 나머지, 많은 경쟁자들이 그녀의 화풍을 따라 하고 있다. 실제로 경쟁자 중 하나인 무네(Moonet)는 피카우소의 그림을 정확히 복제하려 하고 있다!
피카우소는 자신의 그림 하나를 복제하는 데 시간이 얼마나 걸릴지 궁금해한다. 그녀가 생각하기에, 복제를 하려면 서로 겹치지 않는 직사각형들의 모음을 캔버스에 칠할 수 있다(겹치면 물감이 섞이기 때문이다). 이것들이 마르기를 기다린 뒤, 다시 서로 겹치지 않는 직사각형들의 모음을 칠할 수 있다. 첫 번째 직사각형 모음은 이제 말라 있으므로, 새 직사각형 모음은 첫 번째 모음과 겹쳐도 된다. 이런 식으로 각 라운드마다 서로 겹치지 않는 직사각형들의 집합을 칠하고 마르기를 기다리는 과정을 반복한다. 전체 과정에서 각 색의 직사각형은 최대 한 번만 그릴 수 있는데, 그렇지 않으면 결과물이 진정한 피카우소 화풍이 아니게 되기 때문이다.
주어진 피카우소의 그림을 복제하는 데 필요한 최소 라운드 수를 구하시오.
문제 출처: Brian Dean
문제 출처: Brian Dean
입력의 첫째 줄에 캔버스의 크기 \(N\)이 주어진다 (\(1 \leq N \leq 40\)). 다음 \(N\)개의 줄은 캔버스의 최종 그림을 나타내며, 각 줄에 \(0 \ldots N^2\) 범위의 정수 \(N\)개가 주어진다. 입력은 위에서 설명한 대로 서로 다른 색의 직사각형을 차례로 칠해 그려졌음이 보장된다.
주어진 그림의 복제본을 만드는 데 필요한 최소 라운드 수를 출력한다.
art.in · 출력을 쓸 파일 art.out4
2 2 3 0
2 7 3 7
2 7 7 7
0 5 5 53In this example, round one consists of drawing rectangles of colors 2 and 5.
Round two involves drawing the rectangle of color 7, and the third and final
round involves drawing the rectangle of color 3 (of course, the rectangle of
color 5 could have been drawn during rounds 2 or 3 also).