[백준/JAVA] 8980번: 택배

📖 문제

8980번: 택배

 

 

 

💡  풀이 방식

• 그리디 + 정렬

필요 자료구조
- (보내는 마을, 받는 마을, 박스 개수) 정보를 갖는 객체
- 각 마을 별 받는 박스 개수를 기록하는 1차원 int형 배열

 

1. M개의 보내는 박스 정보를 입력받아 객체 배열에 저장한다.

info = new Info[M + 1];
for(int i = 1 ; i <= M ; i++) {
    st = new StringTokenizer(br.readLine(), " ");
    int from = Integer.parseInt(st.nextToken());
    int to = Integer.parseInt(st.nextToken());
    int box = Integer.parseInt(st.nextToken());

    info[i] = new Info(from, to, box);
}

 

 

2. 객체 배열의 값을 보내는 마을 기준 오름차순 정렬한다.

Arrays.sort(info, 1, M+1);

/*
class Info implements Comparable<Info> {
    int from, to, box;

    public Info(int from, int to, int box) {
        this.from = from;
        this.to = to;
        this.box = box;
    }

    @Override
    public int compareTo(Info i) {
        if(this.to == i.to)
            return this.from - i.from;
        return this.to - i.to;
    }
}
*/

 

 

3. 마을 별로 받을 수 있는 박스 갯수 배열 capacities에 택배 용량 C만큼 저장해둔다.

capacities = new int[N + 1];    // 마을 별로 받는 박스 갯수
for(int i = 1 ; i < N ; i++) {
    capacities[i] = C;
}

 

 

4. M개의 박스 정보 배열을 순회하며 다음과 같이 처리한다.  1) 해당 마을에서 보낼 수 있는 최대 한도를 계산한다.

int max = Integer.MAX_VALUE;    // 보낼 수 있는 최대 한도
for(int j = now.from ; j < now.to ; j++) {
    max = Math.min(max, capacities[j]);
}

 

 

  2-1) 최대 한도가 현재 보내려는 택배 개수보다 크다면, 보내는 마을과 받는 마을 사이 경로 마을 모두 용량에서 현재 보내려는 택배 개수를 뺀다.

if(max >= now.box) {
    for(int j = now.from ; j < now.to ; j++) {
        capacities[j] -= now.box;
    }
    answer += now.box;
}

 

 

  2-2) 그게 아니라면, 위에서 구한 최대 한도 기준만큼만 택배 개수를 뺀다.

else {
    for(int j = now.from ; j < now.to ; j++) {
        capacities[j] -= max;
    }
    answer += max;
}

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,C,M;
    static Info[] info;
    static int[] capacities;    // 마을 별로 받는 박스 개수
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());   // 마을 수
        C = Integer.parseInt(st.nextToken());   // 트럭 용량
 
        M = Integer.parseInt(br.readLine());    // 보내는 박스 정보 개수
 
        // 1. 보내는 박스 정보 입력 후 정렬하기
        info = new Info[M + 1];
        for(int i = 1 ; i <= M ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int box = Integer.parseInt(st.nextToken());
 
            info[i] = new Info(from, to, box);
        }
        Arrays.sort(info, 1, M+1);
 
        // 2. [초기화] 마을들을 택배 용량 C만큼 기록
        capacities = new int[N + 1];    // 마을 별로 받는 박스 갯수
        for(int i = 1 ; i < N ; i++) {
            capacities[i] = C;
        }
 
        int answer = 0;
 
        for(int i = 1 ; i <= M ; i++) {
            Info now = info[i];
 
            // 1) 해당 마을에서 보낼 수 있는 최대 한도 구하기
            int max = Integer.MAX_VALUE;    // 보낼 수 있는 최대 한도
            for(int j = now.from ; j < now.to ; j++) {
                max = Math.min(max, capacities[j]);
            }
 
            // 2-1) 최대 한도가 현재 보내려는 택배 개수보다 크다면
            // 보내는 마을과 받는 마을 사이 경로 마을 모두 용량에서 현재 보내려는 택배 개수 빼기
            if(max >= now.box) {
                for(int j = now.from ; j < now.to ; j++) {
                    capacities[j] -= now.box;
                }
                answer += now.box;
            }
            // 2-2) 그게 아니라면, 위에서 구한 최대 한도 기준
            else {
                for(int j = now.from ; j < now.to ; j++) {
                    capacities[j] -= max;
                }
                answer += max;
            }
        }
 
        System.out.println(answer);
    }
}
 
class Info implements Comparable<Info> {
    int from, to, box;
 
    public Info(int from, int to, int box) {
        this.from = from;
        this.to = to;
        this.box = box;
    }
 
    @Override
    public int compareTo(Info i) {
        if(this.to == i.to)
            return this.from - i.from;
        return this.to - i.to;
    }
}

 

 

 

➕ 다른 풀이 방식

- 개인적으로는 이 풀이가 좀 더 깔끔한 것 같다. ✅

[자바]백준 8980번 택배 [그리디][엄탱]

 

- 조금 다른 풀이!

백준 8980번 :: 택배 (Java)

 

---

💦 어려웠던 점

- 배열,객체 인덱스 처리에서 자꾸 에러가 나서 좀 혼란스러웠다,,

- 1번부터 N번 마을까지 돌면서 박스를 보내고, 싣고 하는 방법을 생각했는데 이게 아니었다. (이래서 인덱스 에러가 난 것 같음)

- 문제를 제대로 이해하지 못했던 것 같다,ㅎ

 

 

🧐 새로 알게 된 내용

- 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[BOJ] 백준 8980번 : 택배 (JAVA)