백준 8980번 택배

문제 링크입니다: https://www.acmicpc.net/problem/8980

KOI 초등부 문제이지만 제 기준 접근 방법이 어려웠던 그리디(Greedy) 문제였습니다.

알고리즘은 아래와 같습니다.

1. 트럭은 한번 방문한 도시를 다시 방문하지 않고 1번 도시부터 출발하기 때문에  1번 도시와 가까운 순으로 박스를 옮기는 것이 최적입니다.

2. 따라서 도착 도시를 기준으로 오름차순 정렬을 해주고 도착 도시가 같다면 시작 도시를 기준으로 오름차순 정렬을 해줍니다.

3. 시작도시부터 도착도시까지 가장 많이 적재된 박스 양을 구합니다.

4. 3번에서 구한 값에 대해 더 적재할 수 있는 양을 파악하고 결과 값에 더해줍니다.

5. 해당 구간에 4번에 구한 값만큼 더해줍니다.

6. 3~5번을 M번 반복합니다.

결국 이 문제가 그리디 알고리즘인 이유는 1번에서 설명하였듯이 한번 방문한 도시를 다시 방문하지 않기 때문에 트럭이 출발하기 시작하는 도시 즉, 1번 도시에 가까운 도시로 박스를 옮길 경우 최적의 해를 구할 수 있습니다.

(보다 자세한 설명은 plzrun님의 질문 게시판 답변입니다.)

https://www.acmicpc.net/board/view/6327

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 10000 + 1;

 

int N, C, M;

int capacity[2000 + 1]; //idx에서 트럭에 차 있는 박스 양

pair<pair<int, int>, int> arr[MAX]; //출발, 도착, 박스

 

bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)

{

        //도착점 기준

        if (a.first.second < b.first.second)

                 return true;

        //도착점이 동일할 경우 시작점 기준

        else if (a.first.second == b.first.second)

                 if(a.first.first < b.first.first)

                         return true;

        return false;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N >> C >> M;

 

        for (int i = 0; i < M; i++)

                 cin >> arr[i].first.first >> arr[i].first.second >> arr[i].second;

 

        sort(arr, arr + M, cmp);

 

        int result = 0;

        for (int i = 0; i < M; i++)

        {

                 int boxCnt = 0;

                 //해당 구간을 돌면서 가장 많이 적재된 양

                 for (int j = arr[i].first.first; j < arr[i].first.second; j++)

                         boxCnt = max(boxCnt, capacity[j]);

                 //트럭에 더 심을 수 있는 양

                 int leftSpace = min(arr[i].second, C - boxCnt);

                 result += leftSpace;

                 //해당 구간에 더 적재 시킨다

                 for (int j = arr[i].first.first; j < arr[i].first.second; j++)

                         capacity[j] += leftSpace;

        }

        cout << result << "\n";

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~