BOJ 12841 - 정보대 등산

문제 링크(Link)

---

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

문제 해결(Solution)

---

 DP로 문제를 해결한다.

 1. DP[n][chk] : n번 째 지점에서 chk(0 : 횡단 보도를 건너지 않았다 , 1 : 횡단 보도를 건넜다)일 때, 최소 이동거리. 시간 복잡도는 O(N)이 된다.

 3. DP를 구하는 과정이 전체 시간을 결정하므로, 전체 시간 복잡도는 O(N)이 된다.

주의할 점 || 생각해볼 점(Caution || Consideration)

---

 1. 횡단 보도는 한 번만 건널 수 있다. 그 때, 어디를 건너야하는 지도 구해야하는 게 조금 까다로울 수 있다. 전역 변수로 vector를 선언한 후, i번 째 횡단 보도를 건널 때가 건너지 않을 때보다 거리가 작거나 같으면 vector에 삽입한다. 그리고 문제에서 가장 낮은 횡단 보도 번호를 원하므로, 정렬해서 0번 째 인덱스의 값을 출력하면 된다.

참고(Reference)

---

 - 

※ 정확하고 부드러운 태클은 언제나 환영입니다.