[BOJ 5846] Wifi Setup

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

5864번: Wifi Setup

Tag : dynamic programming

 

문제요약

수직선 상에 N개의 점이 존재할 때 이를 모두 덮기 위한 최소 비용을 구하는 것이다.

선분 하나의 설치 비용은 A + Br이다. (r은 선분의 길이/2)

 

풀이

이 문제의 N은 최대 2000이고 크게 \(O(N^2)\), \(O(N)\)의 시간복잡도를 가진 두가지 풀이가 존재한다. 

최적의 해를 만들기 위해 선분의 시작과 끝은 항상 점 위에 존재하고 그래서 쉽게 풀이를 생각해볼 수 있다.

\(dp_i:=\)1~i까지 커버하는 최소 비용 으로 잡는 것이 편해보인다. 

 

+부동소수점 출력을 직접 케이스워크해야한다. 그거만 아니면 괜찮은 문제일텐데...

 

sol1) \(O(N^2)\)

\(dp_i=dp_j + A + (v_i-v_{i-1})/2 * r\)

 

시간복잡도 : \(O(N^2)\)

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

ll N,A,B;
ll v[2020];
ll dp[2020];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>N>>A>>B;
    for(int i=1;i<=N;i++){
        cin>>v[i];
        v[i]*=2;
    }
    sort(v+1,v+1+N);
    for(int i=1;i<=N;i++){
        dp[i]=2*A+(v[i]-v[1])/2*B;
        for(int j=0;j<i;j++){
            rmin(dp[i],dp[j]+2*A+(v[i]-v[j+1])/2*B);
        }
//        cout<<i<<' '<<dp[i]<<endl;
    }
    if(dp[N]%2)cout<<dp[N]/2<<".5"<<endl;
    else cout<<dp[N]/2<<endl;
}

---

sol2) \(O(N)\)

\(dp_i=\max_{1<j<i}(dp_{i-1}+A,dp_{i-1}+(v[i]-v[i-1])/2*r)\)

이전의 점을 덮는 선분을 연장할건지, 또는 새 선분을 만들건지 결정해주면된다.

 

시간복잡도 : \(O(N)\)

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

ll N,A,B;
ll v[2020];
ll dp[2020];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>N>>A>>B;
    for(int i=1;i<=N;i++){
        cin>>v[i];
        v[i]*=2;
    }
    sort(v+1,v+1+N);
    dp[1]=2*A;
    for(int i=2;i<=N;i++){
        dp[i]=min(dp[i-1]+2*A,dp[i-1]+(v[i]-v[i-1])/2*B);
    }
    if(dp[N]%2)cout<<dp[N]/2<<".5"<<endl;
    else cout<<dp[N]/2<<endl;
}