[백준] 20928. 걷는 건 귀찮아

https://www.acmicpc.net/problem/20928

문제요약

• M 지점까지 가는 최소 환승 횟수
• ${p_i}$ 지점마다 ${+x_i}$ 범위 이내는 갈 수 있음. 시작은 ${p_1}$
• N은 10만개, 위치는 100만, x는 1만

접근법

• dp처럼 해야하나 했는데 값이 큼
• bfs로 하면 좋겠는데 가지가 ${N^2}$
• 우선순위큐 접근법
  • ${p_i}$ 지점까지 오는 최소 환승을 구해나가는 방식
  • 환승을 갖고 있는 minpq1
  • 최고이동거리를 갖고 있는 minpq2
  • minpq2에서 ${p_i}$에 못미치는 것들은 제거
  • minpq1에서 제거된것들은 제거
• 그리디 접근법
  • 생각을 못했음
  • ${p_i}$에서 갈 수 있는 인덱스를 찾는데
  • 이전에 처리했던 인덱스 이후부터 찾음
  • N = 10이고, 앞선 처리에서 1, 2, 3까지 도달을 한 경우
  • ${p_i}$ 처리시 4번부터 확인함
  • 투포인터같은 처리임