[도전 10일차] 백준 2300 기지국

※복습 : 

문제 : BOJ 2300 기지국

 

문제 링크

 

사용 알고리즘 : 다이나믹 프로그래밍

 

풀이:

점화식을 세우자.

 

DP(n) 을 1~n번째 기지국까지 보았을 때 기지국 설치비용의 최솟값이라 정의하자.

건물들의 좌표를 x좌표 기준 오름차순으로 정렬했을 때 다음 점화식이 성립한다.

 

$$ DP(n) = \min_{1<=k<=n} [ DP(n-k) + \max ( x_n - x_{n-k}, \max_{n-k+1<=i<=n}abs( 2*y_i ) ) ]$$

일반적으로 이 점화식을 구현하면 $max(abs(2*y_i))$ 부분에서 O(n)이 걸린다.

그러나 항상 n-k+1~n까지의 max를 구해야 하므로

k를 감소시키는 방향으로 DP를 채우면 $amortized \; O(1)$에 처리할 수 있다.

 

점화식을 코드로 구현하자.

 

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end());
const int INF = 1e9;
using namespace std;
int n,DT[10010];
pair<int,int> arr[10010];
int solve(int k){
    if(DT[k])
        return DT[k];
    if(k<=1)
        return DT[k]=abs(2*arr[k].second);
    int ans=INF,ymax=0;
    for(int i=k-1;i>=0;i--){
        ymax=max(ymax,abs(arr[i+1].second));
        ans=min(ans,solve(i)+max(2*ymax,arr[k].first-arr[i+1].first));
    }
    return DT[k]=ans;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>arr[i].first>>arr[i].second;
    sort(arr+1,arr+n+1);
    cout<<solve(n);
}