문제 링크
- https://icpc.me/11475
사용 알고리즘
- DP
- 파라메트릭 서치
- 세그먼트 트리 / 덱
시간복잡도
- O(Nlog2N) 또는 O(NlogN)
풀이
역방향으로 이동하면 항상 손해이므로 항상 번호가 증가하는 정류장만 방문한다고 가정해도 충분합니다. 지하철을 타고 이동하는 시간은 항상 N−1로 일정하므로 환승 시간을 최소화하는 문제라고 생각할 수 있습니다.
범위가 r인 카드는 r−1인 카드가 이동할 수 있는 범위를 포함합니다. 따라서 범위가 r인 카드의 가격을 \min\left{ p_1, p_2, \cdots, p_r \right}이라고 생각해도 됩니다. 이동 범위가 증가하면 가격이 단조 증가하고 소요 시간은 단조 감소하므로 이동 범위에 대한 파라메트릭을 시도할 수 있습니다.
이동 범위를 R로 제한된 상황에서의 최소 소요 시간은 동적 계획법을 이용해 계산할 수 있습니다. i번째 정류장까지 이동하는데 드는 최소 환승 시간을 D(i)라고 하면, D(i)=min이 성립합니다. 단순하게 계산하면 O(N^2)이지만 세그먼트 트리를 이용하면 O(N \log N), 덱을 이용하면 O(N)에 계산할 수 있습니다.
결정 문제를 O(N \log N) 또는 O(N)에 해결할 수 있으므로 전체 문제를 O(N \log^2 N) 또는 O(N \log N) 시간에 해결할수 있습니다.
전체 코드
1 |
|