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;
}'알고리즘 문제풀이 > 그리디' 카테고리의 다른 글
| 백준 1439 [C++] (0) | 2020.10.16 |
|---|---|
| 백준 1969 : DNA (0) | 2020.03.24 |
| 백준 1138 (0) | 2020.02.28 |
| 백준 1049 (0) | 2020.02.23 |
| 백준 1946 (0) | 2020.02.23 |
