https://www.acmicpc.net/problem/31886
요약
- N by N 좌표, M 개의 점
- 가로 또는 세로 한 줄에 K 이하의 점이 있으면 그 줄을 몽땅 지울 수 있음
- 한번의 연산에서 가로(또는 세로) 줄들을 쭉 보면서 K 이하다? => 삭제
- K 이하가 아니다 => 유지
- 가로(또는 세로) 전체를 보는게 한번의 연산
- N,M,K : 200000
- 모두 지울 수 있을까? 최소의 연산 횟수는?
접근법
- 가로를 한번 했으면 다음 차례에는 세로를 함(가로를 두 번 하지는 않음)
- min(가로 먼저 시작, 세로 먼저 시작)
- 가로를 쭉 보고 K 이하인 것들을 찾아서 지우는 작업을 하고, 다음에 세로 작업을 진행
- 그런데 매번 가로/세로를 탐색하면 시간이 오래 걸릴 것임(N^2 시간 소요)
- 대상이 될 것들만 본다
- K 이하인 가로/세로만 후보군에 넣는다
- 언제 K 이하가 되나?
- 처음에 이미 K 이하인 것들
- 연산을 한 후 K 이하가 되는 것들 => 연산을 하면서 새롭게 K 이하가 되는 것들을 후보군에 넣는다
- 삭제 작업은 어떻게 처리하나?
- x 좌표에 들어있는 y 좌표들의 리스트를 유지(반대도 마찬가지)
- x 좌표에 대해 삭제 작업을 진행할때(y 좌표 처리도 마찬가지)
- x 좌표의 count는 0으로 처리
- x에 들어있는 y 좌표에 대해서 count-- 처리
- 이때 이미 0인 것들은 대상에서 제외
- count--를 하면서 K 가 되는 것들은 새로운 후보군에 등록
- 더 이상 후보군이 없으면 작업 중지
- 작업을 다 했는데 아직 남아있는 좌표가 있다? => 실패
- 주의
- 가로 후보군에 대해서 작업을 하고 세로 후보군을 생성할텐데
- 최초에는 세로 후보군은 일괄적으로 한번 훑어줘야함
- 세로에 이미 후보로 들어가야할 것들이 있으므로
- 예시
- 5 5 1
1 1
1 2
2 2
2 3
3 3
구현 Tip
- 임의로 가로[0], 세로[1] 로 표현
- 인접 행렬로 x 좌표에 들어있는 y 들을 처리(반대도 마찬가지)
- 후보군1로 처리를 하고나면 후보군2가 생성(가로를 처리하면 세로 후보군이 생성)
- 후보군2를 대상으로 다시 처리(반복)
newbieski