두 성별을 서로 바꾸어도 만나는 횟수는 바뀌지 않는다. 따라서 더 적은 쪽의 학생 수를 라고 하고, 이 학생들이 차지할 개의 칸을 고른 뒤 나머지 칸을 다른 성별로 채우자. 이면 어느 쪽을 골라도 된다. 이면 격자 전체를 한 성별로 채우면 된다.
일 때 최솟값은 다음 두 값 중 작은 값이다.
는 가 의 배수이면 , 그렇지 않으면 로 정의한다. 각 값에 대응하는 배치를 만들 수 있으므로, 두 값을 비교하여 더 작은 쪽의 배치를 출력하면 된다.
첫 번째 배치는 왼쪽 위에서 정사각형에 가까운 모양을 만든다. , 라고 하자. 먼저 왼쪽 위의 정사각형을 채운다. 이어서 정사각형 바로 오른쪽 열의 위쪽부터 칸을 채운다. 이면 정사각형 바로 아래 행의 왼쪽부터 칸을 더 채운다. 이므로 이 과정에서 정확히 칸을 채운다.
이때 은 제곱근의 소수 부분을 사용하지 않고 계산할 수 있다. 이면 , 이면 , 이면 이다. 정수 는 를 만족하도록 구한다.
두 번째 배치는 첫 번째 행부터 아래로 내려가며, 각 행에서는 왼쪽부터 오른쪽으로 칸을 채운다. 완전히 채운 행들 뒤에 필요하면 일부만 채운 행 하나가 생긴다.
이면 첫 번째 배치를, 아니면 두 번째 배치를 선택한다. 각 행에서 채워야 하는 칸의 수를 바로 계산할 수 있으므로 한 행씩 만들어 출력하면 된다. 출력해야 하는 칸이 개이므로 시간 복잡도는 이고, 한 행을 담는 문자열을 사용하면 공간 복잡도는 이다.
증명
선택한 성별의 칸을 개 칠했다고 생각하고, 색이 다른 두 칸 사이의 변의 개수를 경계의 길이라고 하자. 이는 만나는 횟수와 같다.
먼저 모든 칠한 칸을 각 행의 왼쪽으로 붙인다. 한 행에 칠한 칸과 칠하지 않은 칸이 모두 있으면 원래 가로 방향의 경계가 적어도 하나인데, 왼쪽으로 붙인 뒤에는 정확히 하나이다. 인접한 두 행의 칠한 칸 수가 각각 라면 두 행 사이의 경계는 원래 적어도 개이고, 왼쪽으로 붙인 뒤에는 정확히 개이다. 따라서 이 변형은 경계의 길이를 늘리지 않는다.
Solution written by GPT6
다음으로 칠한 칸 수가 많은 행부터 정렬한다. 가로 방향의 경계 수는 그대로이다. 세로 방향의 경계 수는 인접한 행의 칠한 칸 수 차이의 절댓값의 합인데, 어떤 순서에서도 최댓값과 최솟값의 차이 이상이다. 내림차순으로 정렬하면 정확히 그 차이가 되므로 경계의 길이는 늘어나지 않는다.
정렬한 행들의 칠한 칸 수를 이라 하고, 인 행의 수를 라고 하자. 이 배치의 경계 길이는
이다. 다음 네 경우를 나누어 하한을 구한다.
어떤 배치도 경계를 늘리지 않고 위 형태로 바꿀 수 있으므로, 원래 배치의 경계 길이 역시 이상이다.
첫 번째 구성은 칠한 부분의 높이와 너비의 합이 이며, 각 행의 칠한 칸 수가 내림차순이다. 따라서 경계 길이는 이하이다. 격자의 끝에 닿아 경계가 사라지는 경우에도 이 상한은 성립한다.
두 번째 구성에서 이면 경계 길이는 이다. 이면 첫 행의 일부만 칠하므로 경계 길이는 이다. 따라서 두 번째 구성의 경계 길이는 항상 이하이다.
두 구성 중 작은 상한에 대응하는 배치의 경계 길이는 이하이고, 앞에서 모든 배치에 대해 같은 값 이상의 하한을 증명했다. 그러므로 선택한 배치는 최적이다.
