[백준 2300] 기지국

문제

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

 

알고리즘

동적 계획법

 

풀이

기지국들을 하나의 통신 범위로 묶을 때, $x$ 좌표를 정렬한 후 묶어야 함을 알 수 있습니다. 건물$i$와 건물$j$를 하나의 통신 범위 안에 넣을 때, 사용하는 길이는 두 건물의 $x$좌표 차와 그사이에 있는 빌딩들의 $y$좌표*2 중 최댓값이 되어야 합니다.

 

$cache[i]$= 현재 건물 $i$부터 세워나갈 때, 필요로 하는 최소 길이

 

$solve()$ 함수는 최대 $N$번 호출되고 함수 내부에서 $for$은 최대 $N$번 반복하므로 시간 복잡도는 $O(N^2)$입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef pair<int, int> pii;
vector<pii> vt;
int N,x,y;
int cache[10000];

int solve(int idx) {
    if (idx == N) return 0;
    int& ret = cache[idx];
    if (ret != -1) return ret;
    ret = INT_MAX/2;
    auto [cx,cy] = vt[idx];
    for (int i = idx;i<N;++i) {
        auto [nx, ny] = vt[i];
        cy = max(cy, ny);
        ret = min(ret, solve(i+1) + max(nx - cx, 2 * cy));
    }
    return ret;
}

int main() {
    FAST;
    memset(cache, -1, sizeof(cache));
    cin >> N;
    rep(i, N) {
        cin >> x >> y;
        vt.emplace_back(x, abs(y));
    }
    cout<<solve(0);


    return 0;
}