시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 127 | 38 | 29 | 28.713% |
코코의 초콜릿 기계는 가로와 세로가 4의 배수인 직사각형 모양의 초콜릿을 생산한다. 코코는 이 기계에서 생산된 $M \times N$ 크기의 초콜릿을 $1 \times 2$ 또는 $2 \times 1$ 크기로 나누어 판매하려고 한다. 하지만 어느 날 코코의 친구 $K$($0 \le K \le 4$)명이 놀러 와서 $1 \times 1$ 초콜릿 한 칸씩을 떼어 먹어 버렸다. 남은 초콜릿을 나누었을 때 최대 몇 개의 초콜릿을 얻을 수 있는지 코코에게 알려주자.
첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 그 다음 줄부터 $T$개의 테스트 케이스가 순서대로 주어진다.
각 테스트 케이스의 첫 줄에는 $M$, $N$, $K$의 값이 주어진다. $M$은 초콜릿의 가로의 길이, $N$은 세로의 길이이다. 다음 $K$줄에는 각각의 친구가 떼어 먹은 초콜릿 조각의 위치가 가로 좌표 $m$, 세로 좌표 $n$ 순으로 주어진다. 맨 왼쪽 위 칸의 좌표는 $(1, 1)$이며, 초콜릿 조각의 위치는 중복되지 않는다.
각 테스트 케이스에 대해, 주어진 초콜릿을 나누어 얻을 수 있는 $1 \times 2$ 또는 $2 \times 1$ 초콜릿의 개수의 최댓값을 한 줄에 출력한다.
4 4 4 0 4 4 2 1 1 4 4 4 4 4 1 1 4 4 2 3 3 4 4 4 4 1 2 2 1 3 3 4 4
8 6 6 5
Contest > BOJ User Contest > 초콜릿컵 > 제1회 초콜릿컵 F번