[백준 8980] 택배(C++)

택배

링크: https://www.acmicpc.net/problem/8980

 

문제

문제 접근

• 각 마을에서 적재할 수 있는 박스의 최댓값을 구해야한다고 생각했다. 따라서 마을의 번호를 오름차순으로 정렬해서 풀이를 시도했다.
  • 문제는 현재의 최댓값이 전체의 최적해일 수 없다는 점이다.
    • 200의 용량을 가진 택배가 마을 1에서 7마을로 가는 200의 상자를 실어버리면 2마을과 4마을의 400을 놓치게 된다.
    • 현재 위치에서의 최적해를 판단하기 위해서는 잠재적으로 얻을 수 있는 값을 알고 있어야 한다.

• 이 문제를 해결할 수 있는 방법을 생각해보자.
  • 최대 적재량이 200이기 때문에 2마을과 4마을에서 180을 싣더라도 20의 여유 공간이 생긴다.
  • 따라서 1마을에서 1마을에서 7마을까지의 여유 공간, 20을 구할 수 있어야 한다.
  • 이 예제에서는 380(180 + 180 + 20)이 최댓값이다.

풀이 힌트

• 정렬의 기준이 중요하다.
  • 시작하는 마을을 기준으로 정렬한다면 시작하는 마을만 보고서 전체의 최적해를 구할 수 없기 때문에 문제가 생긴다.
  • 도착하는 마을을 기준으로 정렬을 하고, 이를 잘 활용해보자.
• 도착하는 마을을 기준으로 정렬할 경우 고려해야하는 문제
  • 상자를 싣는 마을 - 상자를 내리는 마을의 적재량을 가지고 있어야 한다.
  • 상자를 내릴 때 트럭의 현재 적재량을 가지고 있는 것만으로는 문제를 해결할 수 없다. 
• 구간 별 적재 가능한 최댓값을 구하기 위한 배열을 통해 간단히 풀 수 있다.
  • 내리는 마을을 먼저 정렬할 경우 2, 3, 180 | 4, 5, 180 | 1, 7, 200 로 정렬할 수 있다.

• 마지막 1, 7, 200을 보자.

• 여기서 포인트를 정리해보자
  • 마을에 가장 빨리 내리는 순으로 정렬
  • 현재 요소의 구간에서의 최댓값 확인
  • 실을 수 있는만큼 싣는다.
  • 해당 구간의 최댓값 테이블을 채워준다.

코드

#include <bits/stdc++.h>

using namespace std;
int N, M, C;

typedef struct s_info {
    int s;
    int e;
    int amount;
} info;

info vil[100001];
int limit[100001];
queue<pair<int, int> > Q;

bool compare(const info &lhs, const info &rhs) {
    if (lhs.e != rhs.e)
        return lhs.e < rhs.e;
    if (lhs.s != rhs.s)
        return lhs.s < rhs.s;
    return lhs.amount < rhs.amount;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> C >> M;

    for (int i = 0; i < M; ++i) {
        cin >> vil[i].s >> vil[i].e >> vil[i].amount;
    }

    sort(vil, vil + M, compare);

    int mx = 0;
    for (int i = 0; i < M; ++i) {
        int take, cap_max = 0;

        for (int j = vil[i].s; j < vil[i].e; ++j) {
            cap_max = max(cap_max, limit[j]);
        }

        if (cap_max >= C) continue ;
        else if (C - cap_max < vil[i].amount) {
            take = C - cap_max;
        } else {
            take = vil[i].amount;
        }
        mx += take;
        for (int j = vil[i].s; j < vil[i].e; ++j) {
            limit[j] += take;
        }
    }

    cout << mx;
}

※ 오류나 개선점이 있다면 알려주세요 :) 신속히 수정하겠습니다.