https://www.acmicpc.net/problem/25713
문제 요약
- N, M 격자 (1,1) -> (N,M)으로 이동함. (1000, 1000)
- CCTV가 2000개 있음. 직사각형 모양
- 오른쪽/아래로만 이동 가능
- CCTV 최소로 걸리게 이동(문제에서는 CCTV 제거를 물어봤는데 그게 그거)
접근법
- 오른쪽/아래로만 이동하니 dp를 섞어서 최소로 현 지점까지 최소로 걸리고 오는 방법을 찾으면 될 것 같음
- 그런데 CCTV 있는 영역을 다 "색칠" 해보자니 엄청 많음
- 게다가 한번 걸렸는데 또 걸렸다는걸 체크안하려면 칸마다 어떤 cctv인지 체크하고 비교하고... 이것도 이상함
- 이미 걸렸으면 오른쪽, 아래는 두번 체크할 필요는 없음 => 언제 CCTV에 최초로 걸리나??
- 앞선 아이디어를 확장하면 "경계" 를 생각할 수 있음
- CCTV의 위/왼쪽에 닿는 순간 CCTV count + 1이 된다고 볼 수 있음
- 즉 (1,1)부터 이동을 시키는데, 오른쪽으로 이동했을때 CCTV에 새롭게 걸리는지, 아래로 이동했을때 CCTV에 새롭게 걸리는지 를 알 수 있음!
- 그리고 DP 이용
newbieski