[백준] 2300번 기지국

[적용한 알고리즘]

DP

[아이디어]

dp[i] : i 번째 건물까지 지었을 때 비용의 최솟값

으로 정해놓고 생각하자,

 

[생각의 흐름 / 절차] 

dp[i] = min(dp[i], dp[j - 1] + cost) 이고

cost : j ~ i 까지 기지국 비용

 

[교훈]

내용

 

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    int n; scanf("%d", &n);
    vector<pair<int, int>> P(n + 1);

    for (int i = 1; i <= n; i++){
        scanf("%d %d", &P[i].first, &P[i].second);
        if (P[i].second < 0){
            P[i].second *= -1;
        }
    }

    sort(P.begin() + 1, P.end());
    vector<int> dp(n + 1, 100000000);
    dp[0] = 0;

    for (int i = 1; i <= n; i++){
        int up = 0;
        for (int j = i; j >= 1; j--){
            up = max(up, P[j].second); // 다 커버쳐야하니까
            int square = max(P[i].first - P[j].first, up * 2);
            dp[i] = min(dp[i], dp[j - 1] + square);
        }
    }

    printf("%d\n", dp[n]);
    return 0;
}