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

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

그리디 알고리즘이란!?

Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다.
탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

 

문제

아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.

 

 

각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한 대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.

• 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
• 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
• 조건 3: 박스들 중 일부만 배송할 수도 있다.

 

너무길어 사이트 참고 바랍니다.

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 이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다. 

 

출력

트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.

 

예제

 

알고리즘 분류

• 그리디 알고리즘
• 정렬

 

문제 설명

해당 문제는 어떻게 요약해서 설명을 해야 좋을지 잘 모르겠어서 간단하게 요약만 했다.

정확한 이해는 문제를 직접 보고 이해하는게 좋을 것 같다.

 

즉, 트럭은 용량이 정해져있고 보내는 마을과 받는 마을이 정해져 있는 박스가 있다.

트럭이 최대로 몇 박스를 배송할 수 있는지 물어보는 문제이다.

 

해설

정말 많이 고생한 문제이다... 근데 한국정보올림피아드 초등부...문제라니... 나를 얼마나 좌절시켜야 되는 거냐ㅜㅜ

 

이 택배 문제의 핵심은 택배 보낼 박스들의 정렬과 각 마을마다 택배차에 실을 수 있는 개수를 기록하고, 마을마다 기록되어 있는 택배차의 남은 용량을 실시간으로 수정하며 현재 택배차가 머무르고 있는 마을에서 보낼 택배박스를 택배차가 가지고 가도 되는지 확인하고 가지고 가면 되는 것이다.

 

정렬

정렬기준 우선 박스를 받는 마을 번호 기준으로 오름차순이며, 받는 마을 번호가 같을 시 보내는 마을 번호 기준으로 오름차 순한다.

 

용량 기록

1. 우선 처음엔 택배가 아무 박스도 실은 게 없으니 마을들을 택배 용량 C만큼 기록해 준다.
2. 마을에 도착하면, 해당 마을에서 박스를 실을 용량이 있는지 체크해 주고 용량이 남는 만큼 박스를 실어준다.
3. 박스를 실어주고 실어준 박스의 목표 마을 전까지 용량을 줄여준다.

 

코드

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken()); // 마을 수
        int C = Integer.parseInt(st.nextToken()); // 트럭용량
        int M = Integer.parseInt(br.readLine()); //박스 정보 개수

        int[][] receivePriority = new int[M][3];

        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 box = Integer.parseInt(st.nextToken());

            receivePriority[i][0] = start;
            receivePriority[i][1] = end;
            receivePriority[i][2] = box;
        }

        Arrays.sort(receivePriority, ((x, y) -> {
            if (x[1] == y[1]) {
                return x[0] - y[0];
            }

            return x[1] - y[1];
        }));

        int[] capacities = new int[N + 1];
        for (int i = 1; i < N; i++) {
            capacities[i] = C;
        }
        
        int ans = 0;
        for (int i = 0; i < receivePriority.length; i ++) {
            int start = receivePriority[i][0];
            int end = receivePriority[i][1];
            int box = receivePriority[i][2];
            
            int capacity = Integer.MAX_VALUE;
            
            for (int j = start; j < end; j++) {
                capacity = Math.min(capacity, capacities[j]);
            }
            
            for (int j = start; j < end; j++) {
                capacities[j] -= Math.min(capacity, box);
            }
                
            ans += Math.min(capacity, box);
        }

        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}