[BAE/<JOON> 문제풀이] 2300. 기지국

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

2300번: 기지국

서론

쓸게 딱히 없다. 정올 기출 치곤 쉬운 것 같다. 요즘 문제 표기난이도랑 실제 체감 난이도랑 너무 안맞아서 그냥 아무거나 풀고 있다.

풀이

라인 스윕이 부가적으로 들어가있다.

건물들을 x축 기준으로 정렬해놓고 건물들을 순차적으로 추가해나가며 최적값을 계산했다.

점화식은 아래와 같다.

현재 건물 i부터 이전 건물 j 사이의 모든 건물을 포함하는 정사각형의 크기는 max(i.x - j.x, max((i ~ j).y * 2) 이다.

현재 건물만 따로 기지국을 건설하는 경우도 있으므로 j의 범위는 1~i로 i를 포함해야 한다.

• DP[i] = min(DP[j - 1] + max(i.x - j.x, max((i ~ j).y * 2))

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
using ll = long long;
const ll mod = 10007;
struct p {
    int x, y;
};
bool cmp(p a, p b) {    
    return a.x < b.x;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n; vector<p> arr(n + 1); vector<int> dp(n + 1, 2100000000);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].x >> arr[i].y;        
        arr[i].y = abs(arr[i].y);
    }
    sort(arr.begin() + 1, arr.end(), cmp);    
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {                
        int mn = 2100000000;
        int mx = -2100000000;
        for (int j = i; j >= 1; j--) {
            int s2 = (arr[i].x - arr[j].x); 
            mx = mx > arr[j].y * 2 ? mx : arr[j].y * 2;
            mn = mn < dp[j - 1] + (s2 > mx ? s2 : mx) ? mn : dp[j - 1] + (s2 > mx ? s2 : mx);
        }
        dp[i] = mn;
        //cout << dp[i] << " ";
    }
    cout << dp[n];
    return 0;
}