https://www.acmicpc.net/problem/8980
<풀이>
1. 입력값으로 주어지는 택배 정보들을 정렬하여, 보낼 수 있는 최대 택배 갯수를 출력합니다.
<해법>
1. 택배 정보들을 정렬하는 방법.
=> 정렬하는 방법으로 가장 먼저, 보내는 마을 번호 순으로 정렬을 생각할 수 있습니다. 하지만 이렇게 정렬할 경우, 중간지점에서 많은 택배를 배송할 수 있음에도 이미 가지고 있는 택배 때문에 많은 택배를 배송하지 못하는 경우가 생깁니다. 아래 그림과 같은 경우가 그 예 입니다.
1번 마을에서 50개를 담지않고 2,3,4번 마을 박스를 담았다면 150개를 배송할 수 있습니다.
따라서, 정렬은 받는 마을 순으로 해야합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
struct box {
int str;
int fin;
int boxCnt;
};
int N, C, M;
vector<box> v;
int town[2001];
int res = 0;
bool cmp(const box& lhs, const box& rhs) {
if (lhs.fin == rhs.fin) {
return lhs.str < rhs.str;
}
return lhs.fin < rhs.fin;
}
int main() {
//입력
cin >> N >> C >> M;
for (int i = 0; i < M; i++) {
int str, fin, boxCnt;
cin >> str >> fin >> boxCnt;
v.push_back({ str,fin,boxCnt });
}
//마을마다 트럭에 담긴 박스 갯수(0으로 초기화)
memset(town, 0, sizeof(town));
//배열 정렬 -> 도착지점이 작은 순으로 정렬
sort(v.begin(), v.end(), cmp);
for (int i = 0; i < M; i++) {
int str = v[i].str;
int fin = v[i].fin;
int ableBox = v[i].boxCnt;
//지나가는 마을마다 트럭 자리 확인
for (int j = str; j < fin; j++) {
//트럭안에 남은 자리 > 보내려는 박스 -> 박스를 모두 보낼 수 있음
if (C - town[j] > ableBox) {
}
//트럭안에 남은 자리 <= 보내려는 박스 -> 남은 자리만 박스를 보낼 수 있음
else {
ableBox = C - town[j];
}
}
//지나가는 마을의 트럭 자리 채우기
for (int j = str; j < fin; j++) {
town[j] += ableBox;
}
res += ableBox;
}
//출력
cout << res;
}
|
구현에 대해 알아볼 수 있는 문제였습니다.
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[Python] 백준 10833 - 사과 (0) | 2020.06.21 |
---|---|
[C++] 백준 8981 - 입력숫자 (0) | 2020.04.30 |
[C++] 백준 2512 - 예산 (0) | 2020.04.30 |
[C++] 백준 8979 - 올림픽 (0) | 2020.04.30 |
[C++] 백준 1726 - 로봇 (0) | 2020.04.30 |