[백준] 8980번 택배

[풀이]

처음에 많이 헤맸지만.. 결국 각 마을 마다 실을 수 있는 공간을 체크해나가며 해결할 수 있는 문제였습니다.

 

문제를 해결하기 위해선 우선 도착지를 기준으로 오름차순 정렬 해주어야 합니다. 출발지는 상관 없습니다. 

왜 그런지는 이 후에 제가 설명드리는 과정을 보면 이해할 수 있을 겁니다:)

 

1. 출발지부터 도착지 - 1 까지에서 트럭 잔여용량이 가장 적은 곳 찾기

2. 실을 박스의 수 정하기 (1에서 찾은 잔여용량보다 박스의 수가 많다면 1에서의 결과값만큼 박수 싣기)

3. 출발지부터 도착지 - 1 까지 실을 박수의 수만큼 잔여용량을 줄여주기

 

이렇게 3가지를 차례대로 반복해줍니다.

 

문제상의 예제를 바탕으로 풀이해보겠습니다.

마을	1	2	3
잔여용량	40	40	40

우선, 초기상태 입니다. 마을은 4까지 있지만 4는 어짜피 도착지이니 표기할 필요가 없어서 3까지만 표기하였습니다.

그리고 각 마을에서의 트럭 잔여용량을 전부 최대치로 초기화 해놓습니다. 

 

배송할 목록을 도착지를 기준으로 오름차순 정렬하면 다음과 같겠죠??

1 2 10

1 3 20

2 3 10

1 4 30

2 4 20

3 4 20

이를 바탕으로 위에서부터 차례대로 써먹습니다!! ㅎㅎ

마을	1	2	3
잔여용량	40 - 10 = 30	40	40

 1 2 10 

1. 마을 1 <= x < 2에서 제일 적은 잔여용량은 40.

2. 실을 용량(10) < 잔여용량(40) 이므로 전량(10) 싣기.

3. 마을 1 <= x < 2 까지 실은 박스 수만큼 빼주기.

--> 현재까지 운반한 박스 수 = 10

마을	1	2	3
잔여용량	30 - 20 = 10	40 - 20 = 20	40

 1 3 20 

1. 마을 1 <= x < 3에서 제일 적은 잔여용량은 30.

2. 실을 용량(20) < 잔여용량(30) 이므로 전량(20) 싣기.

3. 마을 1 <= x < 3 까지 실은 박스 수만큼 빼주기.

--> 현재까지 운반한 박스 수 = 30

마을	1	2	3
잔여용량	10	20 - 10 = 10	40

 2 3 10 

1. 마을 2 <= x < 3에서 제일 적은 잔여용량은 20.

2. 실을 용량(10) < 잔여용량(20) 이므로 전량(10) 싣기.

3. 마을 2 <= x < 3 까지 실은 박스 수만큼 빼주기.

--> 현재까지 운반한 박스 수 = 40

 

마을	1	2	3
잔여용량	10 - 10 = 0	10 - 10 = 0	40 - 10 = 30

1 4 30

1. 마을 1 <= x < 4에서 제일 적은 잔여용량은 10.

2. 실을 용량(30) > 잔여용량(10) 이므로 일부분(10) 싣기.

3. 마을 1 <= x < 4 까지 실은 박스 수만큼 빼주기.

--> 현재까지 운반한 박스 수 = 50

 

마을	1	2	3
잔여용량	0	0	30

2 4 20

1. 마을 2 <= x < 4에서 제일 적은 잔여용량은 0

2. 용량 0이므로 옮길 박스가 없음.

--> 현재까지 운반한 박스 수 = 50

 

마을	1	2	3
잔여용량	0	0	30 - 20 = 10

3 4 20

1. 마을 3 <= x < 4에서 제일 적은 잔여용량은 20.

2. 실을 용량(20) < 잔여용량(30) 이므로 전량(20) 싣기.

3. 마을 3 <= x < 4 까지 실은 박스 수만큼 빼주기.

--> 현재까지 운반한 박스 수 = 70

 

이러한 프로세스로 정답은 70!! 

 

만약 도착지가 내림차순이거나 뒤죽박죽이라면 절대 이렇게 진행할 수가 없습니다. 

만약 총 용량 40,

1 5 10

2 3 40

3 4 40

이런 배송지가 있고 이순서대로 진행한다하면 답은 70이겠지만

올바른 답은 마을 2와 3에서 40번씩 옮길 수 있어서 답은 80이 되겠죠? 

이처럼 중간에 있는 마을들이 어떨지 알 수 없기 때문에 도착지를 기준으로 오름차순 필수! 

 

아래는 풀이한 코드입니다 :)

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Delivery {
public:
    int from;
    int to;
    int cnt;
    Delivery(int from, int to, int cnt) {
        this->from = from;
        this->to = to;
        this->cnt = cnt;
    }
};
 
// 도착지 기준 오름차순 정렬!
bool cmp(Delivery a, Delivery b) {
    if (a.to < b.to) return true;
    else return false;
}
 
int main(void) {
    int n, c, m;
    cin >> n >> c >> m;
    vector<Delivery> list;
    vector<int> left(n + 1, c);
    int box_cnt = 0;
    for (int i = 0; i < m; i++) {
        int from, to, cnt;
        cin >> from >> to >> cnt;
        list.push_back(Delivery(from, to, cnt));
    }
    sort(list.begin(), list.end(), cmp);
    
    for (auto d : list) {
        // 제일 공간이 적게 남은 개수 찾기
        int min = left[d.from];
        for (int i = d.from + 1; i < d.to; i++) {
            if (min > left[i]) min = left[i];
        }
 
        // 실을 박스의 수(만약 min보다 많다면 min만큼만 싣기)
        int cnt = d.cnt;
        if (min < cnt) cnt = min;
 
        // 최종 박스 수에 +
        box_cnt += cnt;
 
        // from ~ to - 1 까지 cnt만큼 빈공간 줄이기
        for (int i = d.from; i < d.to; i++) {
            left[i] -= cnt;
        }
    }
    cout << box_cnt;
    return 0;
}
 

 

질문이나 지적사항은 댓글 부탁드립니다:)