[백준] 택배

그리디한 문제가 추천 리스트에 있어서 풀어보았다. 택배에 Capcity 만큼 무게를 담을 수 있는 칸이 존재할때 1번부터 M 번까지 최대한 많은 양의 택배를 담아야 하는 문제다. 얼핏 보면 쉬워 보였는데 읽자마자 까다롭다고 생각한 부분은 박스 중 일부만 배달 할 수 있다는 조건이었다. 이 일부를 선택하는 과정을 잘 생각해봐야 했고 어느 그리디 문제와 같이 최대한 공통적인 부분을 찾는게 중요 했다. 솔직히 생각한 시간을 고려하면 그냥 답을 보고 지나쳐도 됐을 법한 문제였는데 그래도 좀 끝까지 잡고 늘어졌고 결국 다른 사람의 답을 참고했지만 썼던 시간이 아까워서 기록을 남겨보고 싶었다.

내가 그리디 하게 생각했던 부분은 이거였다.

더 많은 목표 지점에 택배를 떨굴것
굳이 Capacity 다 채울만큼 모든 택배를 부분적으로 채울 필요가 없었던것

그리고 가장 첫번째로 생각했던 그리디 방법이 이번에 핵심이다. 아무리 첫번째 포인트에서 많은 양의 택배를 가졌다하더라도 내리는 지점이 끝 지점이면은 중간 지점에서 떨굴 수 있는 모든 택배를 스킵하는것과 마찬가지다. 그렇기 때문에 최대한 그리디하게 버릴 부분은 버리고 담을 수 있는 부분은 담는게 이 문제의 핵심이었다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N, C, M; //N, Capacity, Car Nums 
vector<vector<int>> carList; 
int cars[2001]; 

void Input(){
    cin >> N >> C; 
    cin >> M; 
    for(int i = 0; i < M; i++){
        int a, b, c;
        cin >> a >> b >> c; 
        carList.push_back({a,b,c}); 
    }
}

void Solution(){
    memset(cars,0,sizeof(cars)); 
    sort(carList.begin(),carList.end(),[](vector<int>& a, vector<int>& b){
        if(a[1] == b[1]) return a[0] < b[0]; 
        return a[1] < b[1]; 
    });
    int answer = 0; 
    for(int i = 0; i < M; i++){

        int keepTrack = 0; 
        int start = carList[i][0]; 
        int end = carList[i][1]; 
        int tmpCap = carList[i][2]; 

        for(int j = start; j < end; j++){
            keepTrack = max(keepTrack,cars[j]); 
        }

        int res = min(tmpCap,C - keepTrack);
        answer += res;

        for(int j = start; j < end; j++){
            cars[j] += res; 
        }
        
    }

    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

이 문제는 에전에 Car Pooling 문제와 유사하다고 생각했다. Car Pooling 문제도 Destination 을 위주로 정렬을 해주었고 이 문제도 마찬가지였다. 그렇게 정렬을 해주고 난 후에는 start 와 end 지점 사이에 이미 존재하는 capcity 를 계산해주고 (이 부분이 keepTrack 변수의 존재 이유다) 후에는 최대한 많은 양의 택배를 가지고 있어야 하기 때문에 min 함수를 이용해서 그 구간에 택배를 가지고 오는게 더 이득일지 아니면 내가 가진 Capacity 에서 최대값을 빼주는게 이득일지를 생각하고 계산 해야했다.

골드 2 문제라 그런지 좀 더 어려웠고 도착점 위주의 정렬까지는 생각했어도 저렇게 계산적으로 구간을 어떻게 그리디하게 계산 하는 방법은 아마 몰랐을거 같다. 조금 더 연습해야겠다.

배운점:
1. 그리디 알고리즘
2. 예전 문제 참고