https://www.acmicpc.net/problem/31932
문제 요약
- N개의 빙하, M개의 얼음다리
- 얼음다리는 길이가 d, 앞으로 t초후에 무너짐
- 북극곰은 1번 빙하에서 시작, N번까지 이동
- 1번 빙하에서 최대한 늦게 출발할 수 있는 시각(=먹을 수 있는 최대 연어)
접근법
- K초에 출발했다고 치고, N까지 갈 수 있는지 확인해볼 수 있음
- 각각의 빙하에 최대한 빠르게 간다고 했을 때, 다리를 잘 건너서 N까지 갈 수 있으면 가는거고, 못가면 못 가는 거고
- K를 이분탐색으로 찾아볼 수 있음(일찍 출발할 수록 유리, 늦게 출발할 수록 불리)
접근법2
- 그런데 이렇게 생각해 볼 수도 있음
- N에 연결된 빙하에 늦어도 x초에는 와야함
- 연결된 다리가 t초에 무너지고 길이가 d이면 연결된 빙하에 늦어도 x=t-d에는 도착해야함
- 그 다음 연결된 빙하에 도착해야하는 가장 늦은 시간을 알 수 있음
- 다리의 길이로 반복해서 계산
- 이때 d거리의 다리가 t시간에 무너지면 이전 빙하에는 늦어도 d-t 시간에 도착해야하므로 이 값보다 늦으면 안됨
- 계산된 최소 도착시간이 여러개면 가장 큰 값을 택하는 것이 유리
- 다음 계산할 후보는 도착시간이 가장 큰 것을 선택
- dijkstra랑 비슷한 접근법이고, 끝점에서 역방향으로, 도착시간이 큰 것부터 선택해서 찾아감
- 중간에 음수가 나오면 패스
- 이렇게 해서 1에 늦어도 몇초에 도착하는지 구할 수 있음 => 연어를 이때까지 먹을 수 있음
newbieski