[USACO] 백준 5864 - Wifi Setup

www.acmicpc.net/problem/5864

 

일직선상에 서있는 N(1 <= N <= 2000)마리의 소에게 와이파이를 제공하는 최소 비용을 구해야 하는 문제이다.

 

와이파이 기지를 설치하면 양방향으로 전파가 발생하며 설치비용 A와 단위거리당 전송비용 B가 주어지고 비용 cost는

 

$cost = A + B \times r$ (r은 와이파이 기지의 출력이며 양 옆으로 각각 r만큼의 범위를 전송한 거리로 해석된다.)

 

로 계산된다.

 

출력 r을 0으로 설정하는 경우 와이파이 기지가 설치된 좌표에서만 와이파이를 제공받을 수 있다.

 

예제 입력/출력 에 의하면 와이파이 기지가 설치될 수 있는 좌표는 실수가 될 수 있다.

 

이 문제는 N 번째 소까지 와이파이를 제공하는 최소 비용으로 N + 1 번째 소까지 와이파이를 제공하는 최소 비용을 구해야 하는 것으로 생각할 수 있다.

 

우선 와이파이 기지가 최소 하나가 있어야 와이파이를 제공할 수 있으므로 소[idx] 좌표에 기지를 설치하면 소[idx + 1]까지 와이파이를 제공하는 최소 비용은 다음과 같은 점화식으로 생각할 수 있다.

 

min(와이파이 기지를 소[idx]의 좌표와 소[idx + 1]의 좌표의 중간으로 옮겼을 때 발생 비용, 소[idx + 1]의 좌표에 와이파이 기지를 새로 설치하는 비용)

 

해당 점화식을 동적계획법을 통해 풀면 AC를 받을 수 있게 된다.

 

소의 좌표가 기준이 아니라 가장 마지막으로 와이파이 기지가 설치된 좌표와 비용을 계산할 소의 좌표의 중간으로 옮기는게 올바른 점화식이 아닌가라는 의문이 들 수 있는데, 메모이제이션에 의해 거리 비용이 이미 저장된 상태이므로 계산한 소의 좌표와 계산할 소의 좌표의 중간으로 점화식을 세워도 풀이가 가능하다.

 

참고사항 : cout.precision()을 통해 부동소수점 표현 범위를 늘려야 한다. 그렇지 않으면 어떤 TC에 대해 출력을 지수표기법으로 출력해서 WA판정을 받을 수 있다. 해당 소스에서는 14자리까지 표기하도록 했다.

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> crd;
int n, a, b;
double dp[2000];

double setup(int idx);

int main()
{
    cout.precision(14);
    fill(dp, dp + 2000, -1);
    ios::sync_with_stdio(false);
    
    cin >> n >> a >> b;
    dp[0] = a;

    for (int i = 0; i < n; ++i)
    {
        int x; cin >> x;
        crd.push_back(x);
    }

    sort(crd.begin(), crd.end());
    
    cout << setup(1);
}

double setup(int idx)
{
    if (idx == n)
        return 0.;

    if (dp[idx] != -1)
        return dp[idx];
    
    double &ret = dp[idx];
    ret = 0;
    
    int dist = crd[idx] - crd[idx - 1];
    double edit_cost = (double)b * dist / 2;
    
    ret += min(dp[idx - 1] + edit_cost + setup(idx + 1), dp[idx - 1] + (double)a + setup(idx + 1));
    return ret;
}

 

부동소수점 범위 지정을 하지 않아 오답이 나왔었다.