빼빼로 나눠주기

서브태스크 1 빈칸의 수를 $K$라 하자. 모든 $2^K$가지 방향을 열거한다. 각 경우에 가로 상자가 있는 행과 세로 상자가 있는 열을 표시한 뒤 모든 학생을 검사한다. 시간 복잡도는 $O(2^K N M)$이다.

전체 풀이 모든 행에 빈칸이 있으면 모든 상자를 가로 방향으로 놓는다. 각 학생은 자신의 행에 있는 상자에서 빼빼로를 받는다. 마찬가지로 모든 열에 빈칸이 있으면 모든 상자를 세로 방향으로 놓으면 된다.

두 조건이 모두 성립하지 않으면 빈칸이 없는 행과 빈칸이 없는 열이 각각 존재한다. 그 교차점의 학생에게는 같은 행에서도 같은 열에서도 빼빼로를 줄 수 없다. 따라서 불가능하다. 이로써 판정과 구성이 모두 옳다.

입력과 출력을 포함한 시간 복잡도는 $O(NM)$이고, 격자를 저장하는 공간 복잡도는 $O(NM)$이다.

Solution written by GPT6.1