[ICPC] 백준 2159 - 케익 배달

icpc.me/2159

 

N명의 고객의 위치가 이차원 평면 좌표로 주어지며 그 좌표 (r, c)는 $0 \leq r, c \leq 100000$ 의 범위를 가지고 있다.

 

좌표의 범위가 너무나도 크기에, 선아가 배달을 하러 갈 수 있는 지역을 이차원 배열로 나타낼 수 없고 빵을 받는 고객은 자기 위치와 상 하 좌 우 한칸 떨어진 곳까지 케익을 수령할 수 있다. 또한 고객들이 주문한 순서대로 받길 원한다.

 

이를 통해 선아는 i번째 고객까지 배달을 했으면 무조건 i + 1번째 고객에게 가야되며 i + 1번째 고객에게 케익을 배달할 수 있는 좌표는 갈 수 없는 곳을 제외해 최대 5개가 된다고 정리할 수 있다.

 

고객이 케익을 수령할 수 있는 좌표를 파란 원으로 표시한 모습

 

즉, 선아는 다음 고객으로 갈 때 최대 5개의 좌표만 고려하면 된다. 따라서 가능한 좌표를 배열이나 벡터에 저장하여 다음으로 갈 좌표에 대해 맨하탄 거리가 최소가 되는 방향으로 동적 계획법을 수행하면 된다.

 

이 문제와 비슷한 아이디어를 요구하는 문제로 이것이 있다.

 

전체 코드

#include <iostream>
#include <cmath>
#include <queue>
#include <utility>
#include <cstring>
 
using namespace std;
using ll = long long;
using pii = pair<int, int>;
 
ll dp[100001][5];
pii custo[100001][5];
int mr[4] {1, -1, 0, 0};
int mc[4] {0, 0, 1, -1};
 
int n;
 
inline int mtdist(int r, int c, int n, int m) { return abs(n - r) + abs(m - c); }
ll delivery(int idx, int loca);
 
int main()
{
    memset(dp, -1, sizeof dp);
    cin.tie(0); ios::sync_with_stdio(false);
 
    cin >> n >> custo[0][0].first >> custo[0][0].second;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> custo[i][0].first >> custo[i][0].second;
 
        for (int j = 0; j < 4; ++j)
        {
            int nr = custo[i][0].first + mr[j], nc = custo[i][0].second + mc[j];
 
            if (nr < 0 || nc < 0 || nr > 100000 || nc > 100000)
                custo[i][j + 1].first = custo[i][j + 1].second = 1e9;
            else
                custo[i][j + 1].first = nr, custo[i][j + 1].second = nc;
        }
    }
 
    cout << delivery(0, 0);
}
 
ll delivery(int idx, int loca)
{
    if (idx == n)
        return 0;
    
    ll &ret = dp[idx][loca];
 
    if (ret != -1)
        return ret;
    
    ret = 0;
 
    ll tmp = 1e18;
    for (int i = 0; i < 5; ++i)
    {
        if (custo[idx + 1][i].first == 1e9)
            continue;
        
        tmp = min(tmp, delivery(idx + 1, i) + mtdist(custo[idx][loca].first, custo[idx][loca].second, custo[idx + 1][i].first, custo[idx + 1][i].second));
    }
 
    return ret += tmp;
}