[백준] 8980-택배(C++)

문제링크:https://www.acmicpc.net/problem/8980

8980번: 택배

 

그리디 알고리즘 문제였습니다.

우선 첫번째로 조심하셔야 하는 점은 1.도착지 2.출발지 순으로 오름차순 정렬을 해줘야 한다는 것 입니다.

저는 항상 최선의 선택을 한다는 점에 너무 집중을 해서 1.출발지 2.도착지순으로 정렬을 해서 오답을 받았습니다. ㅠㅠ

 

이때 

4 40

3

1 4 40

2 3 40

3 4 40

과같은 입력이 들어오면 오답처리가 됩니다. (정상출력:80 오답:40)

 

 

1) 따라서 1.도착지 2.출발지 순으로 오름차순 정렬을 해야합니다.

 

2) 정렬 후 m번 반복하며 해당박스들을 받을 수 있는지, 얼마나 들어갈 수 있는지 확인합니다.

( 그러기 위해서는 해당위치에 박스를 얼마나 적재했는지 표시하는 int형 배열이 필요합니다.) -> capacity

 

3) 1. 시작도시부터 도착도시까지 가장 많이 적재된 박스양을 구합니다.

   2. 구한 값을 통해 해당도시에서 받을 수 있는 박스량 만큼 결과 값에 더해줍니다.

   3. 시작도시부터 도착도시까지 적재한 박스양을 capacity에 더해줍니다.

 

3)번과 같은 과정을 m번 반복하며 결과값을 결정하는 것입니다.

 

 

정답코드입니다. 꼭 직접 작성해보세요.

 

 

#include <iostream>
#include <algorithm>
using namespace std;

struct info {
	int sender;
	int reciever;
	int cnt;

	
};

info arr[10000];
int capacity[10001] = { 0 };
int n = 0, c = 0, m = 0;
int result = 0;

bool cmp(info a, info b) {
	if (a.reciever < b.reciever)return true;
	else if (a.reciever == b.reciever)
		if (a.sender < b.sender)
			return true;
		
	return false;
}

int main() {
	
	cin >> n >> c;
	cin >> m;

	for (int i = 0; i < m; i++)
		cin >> arr[i].sender >> arr[i].reciever >> arr[i].cnt;

	sort(arr, arr + m,cmp); //오름차순 정렬 1.도착지 2.출발지 

	for (int i = 0; i < m; i++) { 
		
		int maxcnt = 0;
		for (int j = arr[i].sender; j < arr[i].reciever; j++)  //보내는곳부터 받는곳까지
			maxcnt = max(capacity[j], maxcnt); //capacity의 최대값을 저장합니다. 박스를 얼마나 넣을 수 있는 확인하기 위해

		int val = min(arr[i].cnt, c - maxcnt);
		result += val;
		
		for (int j = arr[i].sender; j < arr[i].reciever; j++) {
			capacity[j] += val; // 이동되면서 해당 공간만큼 할당해주어야 박스가 못 실리겠죠
		}

	}

	
	cout << result << endl;

}