문제 설명
아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.
각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.
- 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
- 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
- 조건 3: 박스들 중 일부만 배송할 수도 있다.
마을의 개수, 트럭의 용량, 박스 정보(보내는 마을 번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 단, 받는 마을번호는 보내는 마을번호보다 항상 크다.
입력
입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다.
출력
트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.
문제 풀이
- 보내는 박스 정보를 입력 후 받는 마을 오름차순으로 정렬한다.
(받는 마을이 동일할 경우 보내는 마을 오름차순) - 정렬된 순서대로 각 택배 정보에서 실을 수 있는 박스 수의 최댓값을 구하고 배송한다.
(보내는 마을부터 받는 마을 전까지 모든 구간에서 박스를 실을 수 있어야 함) - 마지막 배송까지 끝냈을 때 배송한 박스 수를 출력한다.
소스 코드
static class Delivery implements Comparable<Delivery> {
int from, to, cnt;
public Delivery(int from, int to, int cnt) {
this.from = from;
this.to = to;
this.cnt = cnt;
}
@Override
public int compareTo(Delivery o) {
if (this.to == o.to) return this.from-o.from;
else return this.to-o.to;
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(in.readLine());
// 보내는 박스 정보 입력 후 정렬
Delivery info[] = new Delivery[M];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(in.readLine(), " ");
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cnt = Integer.parseInt(st.nextToken());
info[i] = new Delivery(from, to, cnt);
}
Arrays.sort(info);
// 1번 마을부터 마지막 마을까지 가면서 배송
int box[] = new int[N+1];
int max, possible, total = 0;
for (int i = 0; i < M; i++) {
int from = info[i].from;
int to = info[i].to;
int cnt = info[i].cnt;
max = 0;
// 지나가는 구간에 이미 실린 박스의 최댓값
for (int j = from; j < to; j++) {
max = Math.max(max, box[j]);
}
// 실을 수 있는 박스 수
possible = Math.min(C-max, cnt);
total += possible;
for (int j = from; j < to; j++) {
box[j] += possible;
}
}
// 배송할 수 있는 최대 박스 수
System.out.println(total+box[N]);
}느낀 점
하. 하. 하. 사실 이 문제는 생각보다는 빨리 풀었다. 그치만 처음 풀었을 땐 이 풀이가 아니었다. 크~게 보면 비슷한 풀이이긴 하지만 코드가... 다르다 이거랑... 약간 직독직해 느낌의 지저분한 코드😅
대충 말하자면 위에 작성한 풀이는 보내는 박스 정보 전체를 이용해서 정렬하고 배송하는 구간 전체에 실린 박스 개수를 따져보면서 박스 정보 순서대로 배송을 했다면, 처음에 푼 풀이는 보내는 마을 각각에 리스트로 받는 마을, 박스 개수 정보만 저장해서 1번부터 N번 마을까지의 리스트에 저장된 정보를 순서대로 확인하면서 박스를 싣고 트럭이 꽉 찼을 때 배송지가 더 먼 박스가 있을 경우 그걸 빼면서 갔다. (그렇게 짠 코드는 소스 코드 링크에 주석으로 있음)
다시 작성한 코드는 스터디 시간에 스터디원의 풀이를 보고 '우와' 하고 다시 풀어봐야겠다 싶어서 해 본 건데 다음엔 스스로 이렇게 생각해서 풀어보고 싶다! 개인적으로 더 이해하기 쉬워보여서 나중에 코드 다시 볼 때도 더 좋을 것 같고, 다른 문제에 활용하기도 좋을 듯. 힘내서 공부하자~~~(ง •̀_•́)ง
