[BOJ 8980] 택배

[문제] : https://www.acmicpc.net/problem/8980

8980번: 택배

 

[필요 개념]

- 그리디 (Greedy) 알고리즘

 

[풀이]

문제 난이도 치고 (풀이일 기준 Gold 4) 생각보다 풀이 방법이 쉽게 떠오르지 않은 문제였다. 

처음에는 보내는 마을을 오름차순으로 정렬한 후, 현재 트럭에 있는 박스 개수를 계속 비교하면서 더 채울 수 있으면 채우고, 내릴 수 있으면 내리는 방식으로 하였으나 당연히 WA를 받았다. 

다음과 같은 반례가 있었다. 

트럭의 용량이 10이고, M = 3일 때, 

1 4 10

2 3 10

3 4 10

과 같은 입력이 주어진다면, 처음에 1 4 10 입력을 통해서 4번 마을에 도착할 때까지 박스 10개를 계속 보관하게 되므로 답이 10이 나온다. 

하지만 실제로는 2 3 10, 3 4 10 두 입력을 통해서 답이 20이라는 것을 금방 알아낼 수 있게 된다. 

그리디 측면에서 생각해봐도 단순히 보내는 마을을 오름차순 정렬한다고 해서 최적해가 생기지 않으리라고 생각이 든다. 

그렇다면 반대로 도착하는 마을이 빠른 순서대로 정렬을 할 수 있다. 

이 경우에는 그리디 (Greedy) 성질을 만족하게 된다. 

최대한 가까운 곳에 박스를 많이 보낼수록 그 뒤에도 박스를 많이 보낼 수 있게 되고, 따라서 총박스의 개수가 최대가 됨을 짐작할 수 있다. 

 

각 구간에서 트럭이 담고 있는 박스의 개수를 저장하는 배열을 하나 선언하여, 각 입력이 주어질 때마다 

[보내는 마을, 도착하는 마을 - 1] 구간에서 트럭의 여부 공간의 최솟값을 찾아 해당 값으로 구간을 모두 더해준다. 

이 값이 배송하는 박스의 개수가 되므로 최종 답에 또한 더해준다. 

 

 [소스 코드]

#define all(v) v.begin(), v.end()
 
using namespace std;
struct box {
    int u, v, num;
};
bool cmp(box &b1, box &b2) {
    if (b1.v == b2.v) return b1.u > b2.u;
    else return b1.v < b2.v;
}
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N, C; cin >> N >> C;
    int M; cin >> M;
    vector<box> v;
    for (int i = 0; i < M; i++) {
        box B;
        cin >> B.u >> B.v >> B.num;
        v.push_back(B);
    }
    sort(all(v), cmp);
    vector<int>A(N + 1);
    int ans = 0;
    for (int i = 0; i < v.size(); i++) {
        int check = 0;
        int temp = MAX;
        for (int j = v[i].u; j < v[i].v; j++) {
            temp = min(temp, min(C - A[j], v[i].num));
         }
        for (int j = v[i].u; j < v[i].v; j++) A[j] += temp;
        ans += temp;
    }
    cout << ans;
}
 

 

사실 이 풀이를 처음 생각했을 때, 해당하는 구간을 모두 갱신해야 하기 때문에 TLE가 뜨지 않을까 고민했었는데, 문제에서 주어지는 입력의 범위가 N이 2000 이하이고, M이 10000 이하이기 때문에 O(NM) 안에 수행이 가능했다. 

만약 N과 M의 범위가 더 커진다면 어떻게 풀이를 할 수 있을지는 자세히 모르겠다.

혹시 아시는 분 있으면 알려주시면 정말 감사합니다,,,

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^