TIL: Maximizing Profit on the Danube River Markets

문제 설명

다뉴브 강을 따라 시장을 방문하며 최대 이익을 얻는 문제이다. 상인은 집에서 출발하여 여러 시장을 방문하고 다시 집으로 돌아오는 여행을 계획한다. 각 시장은 특정 날짜에 열리며, 상인은 시장의 위치, 방문 시 얻는 이익, 그리고 보트를 이용해 이동 시 소모되는 연료 비용(U: 강 상류, D: 강 하류)을 고려해 최적의 방문 경로를 결정해야 한다.

해결 방법

핵심 아이디어

1. 세그먼트 트리:
   • 시장을 위치별로 관리하여, 특정 위치에서 얻을 수 있는 최대 이익을 효율적으로 계산한다.
2. 동적 계획법(DP):
   • 각 시장에 도달했을 때 얻는 최대 이익을 누적 계산하며, 이전 상태를 기반으로 새로운 상태를 업데이트한다.
3. 좌표 압축:
   • 시장의 위치가 최대 (500,001)까지 가능하므로, 이를 압축해 메모리와 계산 효율성을 높인다.

코드

#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 500009;
const int NEG_INF = 0x3f3f3f3f;
typedef pair<int, int> Pair;
typedef vector<pair<int, int>> VectorPair;

// 각 위치별 데이터 저장
VectorPair markers[MAX_SIZE];
int numPoints, upCost, downCost, startPoint;
int upTree[2 * MAX_SIZE], downTree[2 * MAX_SIZE];

// 범위 쿼리 함수
int rangeQuery(int* tree, int left, int right) {
    int maxVal = -NEG_INF;
    for (left += MAX_SIZE, right += MAX_SIZE; left <= right; left >>= 1, right >>= 1) {
        if (left & 1) maxVal = max(maxVal, tree[left++]);
        if (~right & 1) maxVal = max(maxVal, tree[right--]);
    }
    return maxVal;
}

// 단일 업데이트 함수
void updateTree(int* tree, int index, int value) {
    index += MAX_SIZE;
    tree[index] = max(tree[index], value);
    for (; index > 1; index >>= 1) {
        tree[index >> 1] = max(tree[index], tree[index ^ 1]);
    }
}

// upTree와 downTree를 동시에 업데이트
void updateCombined(int position, int value) {
    updateTree(upTree, position, value - upCost * position);
    updateTree(downTree, position, value + downCost * position);
}

// 특정 위치에서 쿼리 수행
int calculateMax(int position) {
    return max(
        rangeQuery(downTree, 0, position) - downCost * position,
        rangeQuery(upTree, position, MAX_SIZE - 1) + upCost * position
    );
}

// 주어진 위치의 데이터를 처리
void processMarkers(VectorPair& currentMarkers) {
    if (currentMarkers.empty()) return;

    sort(currentMarkers.begin(), currentMarkers.end()); // 위치 기준 정렬
    vector<int> upperValues, lowerValues;

    int markerSize = currentMarkers.size();
    for (int i = 0; i < markerSize; i++) {
        int currentMax = calculateMax(currentMarkers[i].first);
        upperValues.push_back(currentMax);
        lowerValues.push_back(currentMax);
    }

    // 아래에서 위로 갱신
    for (int i = 0; i < markerSize; i++) {
        if (i != 0) {
            lowerValues[i] = max(lowerValues[i], lowerValues[i - 1] - downCost * (currentMarkers[i].first - currentMarkers[i - 1].first));
        }
        lowerValues[i] += currentMarkers[i].second;
    }

    // 위에서 아래로 갱신
    for (int i = markerSize - 1; i >= 0; i--) {
        if (i != markerSize - 1) {
            upperValues[i] = max(upperValues[i], upperValues[i + 1] - upCost * (currentMarkers[i + 1].first - currentMarkers[i].first));
        }
        upperValues[i] += currentMarkers[i].second;
    }

    // 최종 업데이트
    for (int i = 0; i < markerSize; i++) {
        updateCombined(currentMarkers[i].first, max(upperValues[i], lowerValues[i]));
    }
}

int main() {
    scanf("%d %d %d %d", &numPoints, &upCost, &downCost, &startPoint);

    // 입력 처리
    for (int i = 0, x, y, z; i < numPoints; i++) {
        scanf("%d %d %d", &x, &y, &z);
        markers[x].emplace_back(y, z);
    }

    // 트리 초기화
    memset(upTree, 0xc0, sizeof(upTree));
    memset(downTree, 0xc0, sizeof(downTree));
    updateCombined(startPoint, 0);

    // 마커 처리
    for (int i = 1; i <= 500001; i++) {
        processMarkers(markers[i]);
    }

    // 결과 출력
    printf("%d", calculateMax(startPoint));
    return 0;
}

코드 설명

1. 트리 초기화:

• upTree와 downTree를 초기화하고, 출발 지점의 위치에서 최대 이익을 0으로 설정한다.

2. 마커 데이터 처리:

• 날짜 순서대로 시장을 처리하며, 위치별로 정렬 후 DP를 이용해 각 위치에서의 최대 이익을 계산한다.
• 아래에서 위, 위에서 아래로 이동하며 가능한 모든 경로를 고려한다.

3. 최종 계산:

• 최종적으로 시작 지점으로 돌아왔을 때의 최대 이익을 출력한다.

So...

이 문제는 동적 계획법과 세그먼트 트리를 활용해, 이동 경로와 이익을 최적화하는 방식으로 해결했다. 시장의 위치와 날짜를 정렬하고, DP를 활용해 효율적인 계산을 수행했다. 특히, 방향성에 따라 비용이 달라지는 점을 고려해 위/아래 방향으로 각각 값을 갱신한 점이 핵심이었다.

이번 문제를 통해 최적화 문제에서 데이터 구조와 DP를 결합하는 기법을 깊이 이해할 수 있었다. 추가적으로, 연료 비용과 이동 거리에 따른 경로 최적화는 현실 세계에서도 활용될 수 있는 흥미로운 문제였다.