문제 문제 링크 BOJ 15249 - Building Bridges 문제 요약 $1$에서 $n$을 잇는 다리를 지어보려 한다. 문제의 비용 발생 정의를 따를 때, 최소로 연결하는 비용을 구해보자.
제한 TL : $3$ sec, ML : $128$ MB $2 ≤ n ≤ 10^5$ $0 ≤ h_i ≤ 10^6$ $0 ≤ |w_i| ≤ 10^6$ 알고리즘 분류 다이나믹 프로그래밍(dp) 볼록 껍질을 이용한 최적화(convex hull trick) 풀이 결국 임의의 위치 $i$까지 다리를 지으려면 $1$에서 바로 짓냐, $1$에서 중간 지점 $j$를 거치고 $j$에서 오냐 로 구분해 볼 수 있다. (단, $j$까지의 최소 비용이 계산 됐다는 가정 하에.)
$j$ ~ $i$에 존재하는 기둥들의 $Σw$ 만큼 비용.....
