1011: 징검다리

Link : judge.koreatech.ac.kr/problem.php?id=1011

---

1. 문제

• 욕심쟁이 마을에 다니는 잘생긴 광성이(02학번, 컴퓨터공학부)는 하나의 골치꺼리를 가지고 있다.
  그 마을에는 강을 건너기 위해서는 징검다리를 지나가야하는데, 징검다리에 씌여있는 숫자만큼의 금액을 징검다리를 건너는데 지불을 해야 한다.
  만약 징검다리에 씌여있는 숫자가 {3, 2, 9, 1, 4, 8, 1, 2, 3, 1} 이고, 점프력이 3이라고 하면 {3, 2, 9, 1, 4, 8, 1, 2, 3, 1}  을 밟아 최솟값 5로 다리를 건널 수 있다.
  강건너 여자친구를 만나러 갈 때마다 너무많은 비용을 지불하고 있는 광성이를 위해, 징검다리를 건너가는데 드는 최소 비용을 구해주자.  단 광성이의 최대 점프력은 3으로 고정되어 있다고 가정한다.

 

---

2. 문제의 조건

• 0 <= 징검다리 길이 <= 10,000
• 0 <= 가중치(소요 금액) <= 100

 

---

3. 문제 접근

• 시간복잡도
  
  시간제한 1초에 case가 10,000이므로 O(N^2)이내의 시간으로 풀어야합니다.
  처음에는 "최소비용"이라고 생각하여 "최소비용신장트리"를 사용해야 하는 줄 알았습니다.
  
  Prim MST 알고리즘은 우선순위 큐를 사용한다면 O(E log V)의 시간 복잡도, Kruskal MST 알고리즘은 O(N log N)의 시간복잡도를 가지고있습니다. 시간복잡도면 보면 풀릴 수도 있다고 생각하였지만 그렇게 되지 않았습니다. 고찰은 추후에...
  그래서 조언을 얻어서 얻은 결과가 이 문제는 DP유형 이라는 것입니다.
  
  
• 아이디어
  
  최대 점프력이 3이므로 dp[0~2]은 [3, 2, 9]가 됩니다. 이때 d[3]로가는 최소 비용은 min(dp[3-1], dp[3-2], dp[3-3]) + arr[3] 가 성립되므로 점화식 d[i] = min(dp[i-1], dp[i-2], dp[i-3]) + arr[i] 가 됩니다.
  
  즉, DP는 O(N)의 시간복잡도로 해결할 수 있게됩니다.

 

---

4. 풀이 방법

• dp[0~2]까지 기존의 데이터를 삽입합니다.
• 점화식에 따라 idx = 3 -> len(arr)까지 전부 탐색합니다
• "끝점"에 도달하는 것이 목표가 아닌, 끝점을 넘을 수만 있다면 되므로 [5 3 8] (end_point) 경우 저 다리를 건널 수 있는 위치는 arr-2 위치이므로 최종점은 dp[-1], dp[-2], dp[-3]중 최소값으로 정해주시면 해결할 수 있습니다.
• 또한, 다리의 길이가 2 이하일 경우 당연히 건너는 최소비용은 0이 됩니다.

 

---

5. 소스코드

• cjw-git.tistory.com/20

 

---

 

cjw.git@gmail.com