https://www.acmicpc.net/problem/8980

 

8980번: 택배

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

www.acmicpc.net

<풀이>

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, 0sizeof(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

+ Recent posts