[백준 / 골드2] 8890 택배 (Java)

문제 보기

사용한 것

• 보낼 수 있는 택배의 최대 수를 구하기 위한 그리디

풀이 방법

• to 기준으로, to가 같으면 from 기준으로 오름차순 정렬한다.
• 각 마을당 보낼 수 있는 최대 수를 c로 초기화한다.
• 오름차순 정렬한 packets를 순회하며 다음 단계를 수행한다.
  • maxNumPerTown과 packet의 to, from을 사용하여 보낼 수 있는 최대 수(maxNum) 설정
    • 보낼 수 있는 최대 수는 경로 중 가장 작은 값과 같음
  • packet의 num과 maxNum 중 더 작은 값 선택
  • packet의 to, from 사이 마을의 maxNumPerTown 감소
    • 선택한 택배가 배송될 때까지 그만큼 경로에서 택배를 실을 수 없음
  • 이번에 선택한 값만큼 answer 증가

코드

public class Main {

    public static void main(String[] args) throws Exception {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(br.readLine());
        Packet[] packets = new Packet[m];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int boxNum = Integer.parseInt(st.nextToken());
            packets[i] = new Packet(start, end, boxNum);
        }

        // 그리디 위한 정렬
        Arrays.sort(packets);

        // 각 마을당 보낼 수 있는 최대 수 초기화 (마지막 마을은 못보냄)
        int[] maxNumPerTown = new int[n + 1];
        for (int i = 1; i < n; i++) {
            maxNumPerTown[i] = c;
        }

        // 그리디
        int answer = 0;
        for (int i = 0; i < m; i++) {
            Packet packet = packets[i];

            // 보낼 수 있는 최대 수 설정
            int maxNum = maxNumPerTown[packet.from];
            for (int j = packet.from + 1; j < packet.to; j++) {
                maxNum = Math.min(maxNumPerTown[j], maxNum);
            }

            // 택배 수와 최대 수 중 더 작은 값
            int num = Math.min(packet.num, maxNum);

            // 각 마을당 보낼 수 있는 최대 수 감소
            for (int j = packet.from; j < packet.to; j++) {
                maxNumPerTown[j] -= num;
            }

            answer += num;
        }

        System.out.println(answer);

        br.close();
    }
}

class Packet implements Comparable<Packet> {

    public int from;
    public int to;
    public int num;

    public Packet(int from, int to, int num) {
        this.from = from;
        this.to = to;
        this.num = num;
    }

    @Override
    public int compareTo(Packet o) {
        if (to == o.to) {
            return from - o.from;
        }
        return to - o.to;
    }
}