'그리디 알고리즘' 태그의 글 목록

www.acmicpc.net/problem/8980

8980번: 택배

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이

www.acmicpc.net

1. 풀이방법

- 그리디 문제인데 매우 까다로웠다...

- 처음에 문제의 설명 방식대로 구현을 하다 보면 반례도 잘 떠오르지 않고 매우 어려웠다...

- 결국 참고한 게시판의 답변입니다

(www.acmicpc.net/board/view/6327) 게시판의 plzrun 님의 답변을 보면

- 왜 도착지를 기준으로 정렬을 해야하는 지를 잘 알 수 있다.

- 처음 구현한 것도 앞마을 부터 차례대로 박스를 올리는데 뭐가 틀렸지? 를 한참 생각했지만...

- 문제점은 출발마을을 앞부터 차례대로 기준으로 삼으며 도착지가 가까운 마을 부터 박스를 올린 것이다.

- 핵심은 1,2,3,... 시작마을부터 차례대로 살피는게 아닌 무조건 도착지가 앞 쪽인 택배박스 부터 올려야 최대의

양을 배달 할 수 있다.

2. 주의사항

- 위의 것을 깨닫고도 구현을 생각하는 것도 꽤나 까다로웠습니다..(저는...ㅠㅠ)

- 문제의 시작부터 마을을 살피는 것으로 생각해서 그 생각에서 벗어나기가;;;

- 결국 해결한 것은 마을에서의 트럭의 가용용량을 배열로 선언해 저장하고, 박스들을 살펴가며

마을 별 가용용량을 조절해주는 식으로 구현하였습니다.

3. 나의코드

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

struct box {
	int start;
	int end;
	int weight;
};
int N,C; //마을의 수 , 트럭의 용량
int M; // 박스정보의 수
int x, y, weight;
int result;
int truck[2001]; //마을 별 트럭의 공간을 표시하기 위해서 (트럭에 올라가있는 박스의 상태)

bool compare(box &lhs, box &rhs) {
	if (lhs.end < rhs.end) return true;
	else if (lhs.end == rhs.end) {
		if (lhs.start <= rhs.start) return true;
		else return false;
	}
	else return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> C; //마을 수 와 트럭의 용량
	cin >> M;
	vector<box> sendbox(M);
	for (int i = 0; i < M; i++) {
		cin >> sendbox[i].start >> sendbox[i].end>>sendbox[i].weight;
	}
	sort(sendbox.begin(), sendbox.end(), compare);

	for (int i = 0; i < M; i++) {
		int cnt = 0;
		for (int j = sendbox[i].start; j < sendbox[i].end; j++) {
			cnt = max(truck[j], cnt);
		}
		result += min(sendbox[i].weight, C - cnt); //박스를 올리자 (담을 수 있는 양이 더 적으면 그 만큼만 올릴 수 있다)
		for (int j = sendbox[i].start; j < sendbox[i].end; j++) { //그 만큼 지나가는 마을에서의 트럭의 용량에서 빼줌
			truck[j] += min(sendbox[i].weight, C - cnt);
		}
	}
	cout << result << "\n";
	return 0;
}