BOJ 8980 - 택배

www.acmicpc.net/problem/8980

8980번: 택배

 

골드4라서 그렇게 고난이도는 아닐거라 생각했는데, 꽤나 어려운 문제였다.

 

처음에는, 출발지를 기준으로 오름차순 정렬해서 박스를 배송해야된다고 생각했는데, 그렇게 될 경우 아래 같은 반례에 막혀서 풀 수 없게 된다.

 

4 40

3

1 4 40

2 3 40

3 4 40

 

wrong : 40

correct : 80

 

출발지를 기준으로 오름차순 정렬하면 1번에서 4번 가고 끝이지만, 더 자세히보면 2 -> 3 -> 4 가면 더 많은 양을 배송할 수 있게 된다.

그래서 정렬 기준이 출발지를 기준으로 하는게 아니라, 도착지를 기준으로 먼저 오름차순 정렬하고 출발지를 오름차순 정렬하는 방식으로 바꿔야한다.

(오름차순으로 정렬하는 이유는, 왼쪽에서 오른쪽으로 밖에 못가기 때문이다. 다시 되돌아가는게 없음, 한번가면 끝임)

 

 

이 문제는 정렬뿐 아니라 구현 부분도 마냥 쉽지는 않았다.

정렬한 이후에, 최대로 적재할 수 있는 박스의 양을 구해내야하는데,

 

먼저 각 마을에서 적재한 양을 담는 int capacity[] 배열을 만들고,

M 회 반복문을 순회하는데 (박스 입력 정보만큼 순회)

각 회차에서 시작지점에서 부터 도착지점까지 가장많이 적재된 양을 구하고,

가장 많이 적재된 양을 가지고 트럭에 더 실을 수 있는 양을 구한다

그리고 나서 적재시킬 양을 capacity 배열을 갱신하여서 기록한다.

 

해당 마을에 적재된 양을 담는 배열 int capacity[] 를 선언해서 처리해주는게 

이문제의 주요포인트 중 하나였다.

 

 

- c++

#include <bits/stdc++.h>
 
#define MAX 10001
 
using namespace std;
 
struct Info {
    int from, to, cnt;
};
 
int N, C, M, answer; // 마을 수, 트럭용량, 박스정보갯수 
Info arr[MAX]; 
int capacity[MAX]; // capacity[i] : j => i 번째에서 적재한 양 j 
 
 
// 도착지, 출발지 순으로 정렬 (도착지 우선) 
bool comp(Info& a, Info& b) {
    if (a.to < b.to) return true;
    else if (a.to == b.to) {
        if (a.from < b.from) {
            return true;
        }    
    }
    return false;
}
 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> C >> M;
    for (int i = 0; i < M; ++i) {
        cin >> arr[i].from >> arr[i].to >> arr[i].cnt;
    }
    
    sort(arr, arr + M, comp);
    
    // 전체 박스를 순회하면서 트럭이 담는 최대양 계산 
    for (int i = 0; i < M; ++i) {
        int max_num = 0;
        int from = arr[i].from, to = arr[i].to, weight = arr[i].cnt;
        
        // 시작지 ~ 끝지점에서 가장많이 적재된 양을 구함 
        for (int j = from; j < to; ++j) {
            max_num = max(capacity[j], max_num);
        }
        
        int temp = min(weight, C - max_num); // 더 적재 가능한 양 파악 
        answer += temp;
        
        // 트럭에 적재한 무게 추가 
        for (int j = from; j < to; ++j) {
            capacity[j] += temp; 
        }
    }
    
    cout << answer;
    
    return 0;
}