BOJ-2300 기지국

필요한 지식

1. 동적계획법

접근

• n이 10,000 이므로 $O(n^2)$ 까지 생각해볼수 있다.
• DP[i] 를 i번째 건물까지 포함했을 때의 최소 비용 으로 정의했다.
• $DP[i] = min[ DP[j] + max(v[i].x-v[j].x, maxHeight*2) , for(j:0~i-1)]$ 의 점화식을 얻을 수 있다.

코드(C++)

#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false), cin.tie(),cout.tie();
using namespace std;
int n, dp[10002], y, x;
vector<pair<int, int>> v;

int main() {
    FIO;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        v.push_back({ x, abs(y) });
    }
    sort(v.begin(), v.end());
    fill(begin(dp), end(dp), INT_MAX);
    dp[0] = 0;
    dp[1] = v[0].second * 2;
    for (int i = 2; i <= n; i++) {
        int height = v[i - 1].second;
        for (int j = i - 1; j >= 0; j--) {
            height = max(height, v[j].second);
            dp[i] = min(dp[i], max(height * 2, v[i - 1].first - v[j].first) + dp[j]);
        }
    }
    cout << dp[n];
    return 0;
}

결과