BOJ 14863 - 서울에서 경산까지

문제 링크(Link)

---

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

문제 해결(Solution)

---

 DP로 문제를 해결한다(DP table에 따라서 달라지는 수행 시간 비교).

 1. DP[n][flag][limit] : n번 째 지점 n+1번 째 지점으로 이동 중 flag(0 : 도보 이용 , 1 : 자전거 이용)면서 소요 시간은 limit일 때의 최대 모금액. 

 2. DP[limit] : 소요 시간이 limit일 때의 최대 모금액. 

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

---

 1. 어떻게 3차원 DP table을 1차원으로 줄일 수 있을까? 

  : 항상 최종 목적지에 도착할 수 있는 조건과 1번 지점부터 N번 지점까지 차례로 이동한다는 점과 어느 교통 수단을 이용하든 소요 시간이 K를 넘지만 않으면 된다는 점을 이용하면 줄일 수 있다. 

 2. 시간 복잡도는 얼마나 차이가 날까? 

  : 3차원 DP table을 이용할 때는 input data에 따라서 소요 시간이 달라질 수 있다. 만약 1번 지점부터 N번 지점까지 DP table이 하나도 중복되지 않고, 모든 DP table의 limit 값이 K를 넘지 않는다고 가정한다면 2^100 번의 함수 호출이 일어날 수 있다. 1차원 DP table을 이용할 때는 1번 지점부터 N번 지점까지의 for loop와 K부터 0까지의 for loop의 중첩을 사용하면 O(N*K)만에 문제를 해결할 수 있다. 

참고(Reference)

---

 - 1차원 DP table은 junodeveloper님의 코드를 보고 배웠습니다.

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