Hazel씨는 대학로에서 소극장을 운영중인데, 오늘 밤에는 상하이 연애 조작단 이라는 제목의 연극이 예정되어 있다. 소극장에는 의자가 가로 N개, 새로 M개 격자로 배치되어 있다. 그런데, 요즘은 사회적 거리두기가 한창이라 어느 의자에 누군가 앉아 있으면, 그 의자의 앞, 뒤, 왼쪽, 오른쪽에는 아무도 앉을 수 없다. 대각선에 앉는 것은 가능하다.
최대한 많은 관객을 앉게 하고 싶은데, 아뿔싸. 이미 K명의 관객이 자기가 앉고 싶은 자리에 앉아버렸다. K명의 관객은 사회적 거리두기를 준수하며 앉아 있으나, 그들의 자리를 옮길 수는 없다.
입력으로 N, M, K (N, M은 5이하의 자연수, K는 N*M 이하의 자연수)가 주어진다. 이후 K명의 좌석 정보가 주어진다. 좌석 정보는 좌하단을 (1, 1), 우상단을 (M, N)으로 한다. 현재 상황에서 사회적 거리두기를 유지하며 최대한 더 앉게 할 수 있는 관객의 수를 구하시오.
*회고: O(2^N) 보다 빠른 알고리즘이 있는지? 없다면 없다는 것을 증명할 수 있는지? 제발요.
취미로 알고리즘 문제 만드는 사람