| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 294 | 51 | 45 | 20.548% |
성준이는 무슨 문제든 척척 풀어내는 훌륭한 로봇이다. 이를 시샘한 근수는 성준이가 자는 동안 그의 회로판을 망가뜨렸다.
다행히도 성준이는 자가 치유 프로토콜을 가지고 있어서 이를 이용해 자신을 고쳐보려고 한다. 성준이의 회로판은 $N \times N$ 격자판으로 되어있으며 현재 $M$개의 좌표 $(x_i, y_i)$에 오류가 있다. 성준이는 자신의 회로판을 고치기 위해 다음 2가지 종류의 행동을 반복할 수 있다.
성준이는 모든 오류를 제거해 자신을 빠르게 치유하여 자신을 망가뜨린 근수에게 복수하고 싶어 한다. 최소한의 행동으로 성준이의 모든 오류를 제거하는 방법을 구해보자.
첫 번째 줄에 회로판의 크기 $N,ドル 오류의 개수 $M,ドル 한 줄에서 치유할 수 있는 최대한의 오류 $K$가 공백으로 구분되어 주어진다. (1ドル \le N, M, K \le 2\times10^5$)
두 번째 줄부터 $M+1$ 번째 줄까지 오류의 위치 $(x_i, y_i)$가 공백으로 구분되어 주어진다. (1ドル \le x_i, y_i \le N$)
오류의 위치는 중복되어 주어지지 않는다.
성준이가 모든 오류를 제거하기 위한 최소한의 행동 수를 출력한다. 만약 어떠한 방법으로도 성준이가 자신의 오류를 전부 제거할 수 없다면 -1을 출력한다.
3 4 1 1 1 2 1 2 2 3 2
2
예제 입력 1의 초기 상태 회로판이다. 파란색 칸은 오류를 나타낸다.
행동 2를 실행한다. 첫 번째, 두 번째, 세 번째 세로줄의 오류의 개수는 각각 1,ドル 2, 1$개이다. $K$ 이하의 오류를 가진 첫 번째, 세 번째 세로줄에 있는 모든 오류들을 전부 제거한다.
행동 1을 실행한다. 첫 번째, 두 번째, 세 번째 가로줄의 오류의 개수는 각각 1,ドル 1, 0$개이다. $K$ 이하의 오류를 가진 첫 번째, 두 번째, 세 번째 가로줄에 있는 모든 오류들을 전부 제거한다.
모든 오류가 제거되었고, 이때 행동한 횟수는 총 2ドル$회이다.
2 4 1 1 1 2 1 1 2 2 2
-1
1 1 1 1 1
1
University > 서강대학교 > K512컵 > 2024 서강대학교 K512컵 G번