문제 링크(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)
-
※ 정확하고 부드러운 태클은 언제나 환영입니다.
'Problem Solving > DP' 카테고리의 다른 글
BOJ 9084 - 동전 (0) | 2018.02.26 |
---|---|
BOJ 14863 - 서울에서 경산까지 (0) | 2018.02.11 |
BOJ 1949 - 우수 마을 (0) | 2017.12.21 |
BOJ 1103 - 게임 (0) | 2017.10.30 |
BOJ 12849 - 본대 산책 (0) | 2017.10.07 |