[BOJ/백준][Gold3] 2300 : 기지국 (C++)

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

2300번: 기지국

 

 

[난이도] Gold3
[유형] DP

[풀이]
dp[i] : 1~i번 기지국까지 설치 했을 때의 최소 설치 비용.

dp[i]를 구하기 위해서는 i를 어느 박스에 포함시킬지를 정해야한다.
만약 어떤 j~i를 이은 박스에 포함시키려면 j~i 박스의 최솟값 + dp[j-1] (j-1번까지 설치했을 때의 최솟값)을 더해주면 된다.

점화식
dp[i]= min(dp[i],dp[j-1]+max(2*mH,a[i].first-a[j].first)); (j : 1~i, mH : 1~i까지 높이의 최댓값, a.first : x좌표)

 

 

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int N,dp[10001],inf=9e8;
pair<int,int> a[10001];
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d%d",&a[i].first,&a[i].second);
    sort(a+1,a+N+1);
    for(int i=1;i<=N;i++){
        int mH=0;
        dp[i]=inf;  
        for(int j=i;j>=1;j--){
            mH=max(mH,abs(a[j].second));
            dp[i]=min(dp[i],dp[j-1]+max(2*mH,a[i].first-a[j].first)); 
        }
    }
    printf("%d",dp[N]);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/2300.cpp