백준 8980 택배 Cpp, Java

작성일 | In |

Problem : 택배

유형 : 그리디

문제해석

  • 박스를 최대한 많이 옮길때, 총 박스의 수를 구하라.
  • 어디에서 무슨 택배를 싣고, 내릴지 모든 미래를 이미 알고 있다.

해결전략

  • 가장 많은 박스를 옮기는 방법을 구하는 방법은 시작지 -> 도착지 의 이동거리가 가장 짧은것부터 처리하면 된다.
  • 도착지가 가장 가까운 순으로 정렬한뒤 처리한다.
1
2
3
4
1번 마을 -> 3번 마을 30개
1번 마을 -> 2번 마을 20개

1번 마을 -> 2번 마을 택배를 먼저 처리한다.

구현

  • truckWeight[도시위치] 를 통해서 해당 도시에 위치할때, 트럭이 얼마나 많은 박스를 싣고 있는지 저장한다.
  • 3 to 6 이라는 입력이 있을때, 도시3 - 도시5 까지 (6은 도착지이니 생략한다) 가장 많이 박스가 실려있는 경우를 찾는다.
  • 트럭의 남은 용량(트럭의 최대 용량 - 가장 많이 박스가 실려있는경우), 싣어야 하는 최대 박스중 작은값을 찾아 박스를 싣는다.

코드

Cpp

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
#include <bits/stdc++.h>

using namespace std;

struct DeliveryData {
    int from, to;
    int boxCount;
};

bool cmp(const DeliveryData &d1, const DeliveryData &d2) {
  if (d1.to == d2.to) {
    return d1.from < d2.from;
  }
  return d1.to < d2.to;
}

vector<DeliveryData> deliveryData;
int truckWeight[2002];

int cityCount, truckLimit;
int inputCount;

int answer;


void delivery() {
  for (auto data : deliveryData) {
    int loadedCount = 0;
    for (int i = data.from; i < data.to; ++i) {
      loadedCount = max(loadedCount, truckWeight[i]);
    }

    int loadCount = min(data.boxCount, truckLimit - loadedCount);
    answer += loadCount;

    for (int i = data.from; i < data.to; ++i) {
      truckWeight[i] += loadCount;
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> cityCount >> truckLimit;
  cin >> inputCount;

  while (inputCount--) {
    int from, to, boxCount;
    cin >> from >> to >> boxCount;
    deliveryData.push_back({from, to, boxCount});
  }

  sort(deliveryData.begin(), deliveryData.end(), cmp);
  delivery();

  cout << answer << "\n";

  return 0;
}

Java

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int townCount;
    static int truckCapacity;
    static int answer;
    static int[] truckWeight = new int[2002];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        townCount = Integer.parseInt(st.nextToken());
        truckCapacity = Integer.parseInt(st.nextToken());

        int n = Integer.parseInt(br.readLine());
        List<Load> loads = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());
            loads.add(new Load(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        Collections.sort(loads);
        delivery(loads);
        System.out.println(answer);
    }

    private static void delivery(final List<Load> loads) {
        for (Load load : loads) {
            int alreadyLoadCount = 0;
            for (int spot = load.from; spot < load.to; ++spot) {
                alreadyLoadCount = Math.max(alreadyLoadCount, truckWeight[spot]);
            }

            int canLoadCount = Math.min(load.boxCount, truckCapacity - alreadyLoadCount);
            answer += canLoadCount;

            for (int spot = load.from; spot < load.to; ++spot) {
                truckWeight[spot] += canLoadCount;
            }
        }
    }
}

class Load implements Comparable<Load> {
    int from;
    int to;
    int boxCount;

    public Load(final int from, final int to, final int boxCount) {
        this.from = from;
        this.to = to;
        this.boxCount = boxCount;
    }

    @Override
    public int compareTo(final Load o) {
        if (to == o.to) {
            return Integer.compare(from, o.from);
        }
        return Integer.compare(to, o.to);
    }
}
  • cpp로 푼경우와 java로 푼경우의 시간간격이 3개월이상 나서, 로직은 동일하지만 약간의 변수명 차이가 존재한다.