BOJ 17948 - 뜨끈한 돼지국밥
$O(n^2)$ DP임은 쉽게 보이지만 실제 계산하는게 까다롭다.
내 풀이는 더러워서 공식 풀이를 공부해보자.
아무리 찾아도 공식 풀이를 구할수없다.
...
웰노운 그리디인 $l, r$ 이 있을 때 $\left\lfloor \dfrac{l+r}{2} \right\rfloor$ 의 위치에 무언갈 설치하는 것이 좌우로 거리 차이의 합이 최솟값이라는 점을 이용한다.
위 코드 기준으로 보면 s는 거리의 구간합 배열이고 d,e가 각각 최솟값, 최소 설치 개수인 것 같다.
$i$를 순회하며 $j$ 를 $i$ 아래로 순회하며 중앙에 설치를 하고 그 때의 설치비용이 cur 가 된다.
그것으로 구한 답이 최적이라면 d[j] 로 j 까지 봤을때의 정답에 현재 정답을 더해서 갱신시킨다.
Comments