[백준] 8980번 택배

문제: 8980번: 택배

 

틀린 풀이: 15점

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, c; // 마을 수, 트럭의 용량
	cin >> n >> c;

	int m; // 보내는 박스의 정보 개수
	cin >> m;

	// 보내는 마을 번호를 인덱스로 이용..
	// 0번 인덱스는 안 쓸 것..
	vector < vector<pair<int, int>>> infos(n + 1);
	for (int i = 0; i < m; i++) {
		int from, dest, boxs;
		cin >> from >> dest >> boxs;
		
		infos[from].push_back(make_pair(dest, boxs));
	}

	for (int i = 1; i < n + 1; i++) {
		// 받는 마을 번호를 기준으로 오름차순 정렬(번호가 더 작은 마을의 박스부터 담아야하니까..)
		sort(infos[i].begin(), infos[i].end());
	}


	// 각 도착 마을에 보낼 박스 개수(현재 트럭에 들어있는)
	vector<int> destBoxs(n + 1); // 0번 인덱스 안 써
	int curC = 0; // 현재 트럭에 찬 박스 개수
	int answer = 0;
	for (int i = 1; i < n + 1; i++) {
		int from = i;

		curC -= destBoxs[from]; // 마을에 도달하면 트럭에 있는 박스 개수 빼주기
		answer += destBoxs[from];
		destBoxs[from] = 0; // 요기 마을에 전달할 박스 개수 0으로 바꿔줌..
		
		for (pair<int, int> info : infos[i])
		{
			int dest = info.first;
			int boxs = info.second;

			// 트럭의 용량보다 (현재 용량 + 새 박스들) 의 개수가 작다면 트럭에 그대로 넣기 가능
			if (curC + boxs <= c) {
				curC += boxs;
				destBoxs[dest] += boxs;
			}
			// 트럭의 용량보다 (현재 용량 + 새 박스들) 의 개수가 크면 가능한 만큼만 넣기
			else {
				int possible = c - curC;
				if (possible < 0) continue; // 이 경우는 넣을 수 없으니까 패스..
				destBoxs[dest] += possible;
				curC += possible;
			}
		}
	}
	cout << answer << "\n";


	return 0;
}

 

 

맞은 풀이:

#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;
}

 

 

 

참고자료:

[백준] 8980번 택배

[백준] 8980번 택배

백준 8980번 - 택배

백준 8980번 - 택배

https://chatgpt.com/share/67511cf6-36d4-8003-9314-940ae8cffb4c

ChatGPT - 백준 8980 최적화