상세 컨텐츠

본문 제목

백준# 8980 택배

C#/알고리즘

by McRobbin 2020. 8. 16. 17:51

본문

https://www.acmicpc.net/problem/8980

 

8980번: 택배

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이

www.acmicpc.net

그리디 알고리즘으로 분류된 8980번 택배 문제 입니다.

 

생각 보다 어려웠네요..?

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _8980
{
    public class Deliver : IComparer<Deliver>
    {
        public int start;
        public int end;
        public int count;
 
        public Deliver(int start, int end, int count)
        {
            this.start = start;
            this.end = end;
            this.count = count;
        }
 
        public int Compare(Deliver deliver1, Deliver deliver2)
        {
            return deliver1.end == deliver2.end ? deliver1.start.CompareTo(deliver2.start) : deliver1.end.CompareTo(deliver2.end);
        }
 
        //택배 갯수 출력 함수.
        public void Print()
        {
            Console.WriteLine("start : " + this.start + " end : " + this.end + " count : " + this.count);
        }
    }
 
    public class Truck
    {
        public int maxCount;
        public int curCount;
        public int deliveredCount;
        public List<Deliver> deliverList;
 
        public Truck(int maxCount)
        {
            this.maxCount = maxCount;
            this.curCount = this.deliveredCount = 0;
            
            this.deliverList = new List<Deliver>();
        }
 
        public void DeliverProcess(Deliver deliver)
        {
            this.DoDeliver(deliver.start);
            this.Insert(deliver);
        }
 
        public void Insert(Deliver deliver)
        {
            var index = deliverList.BinarySearch(deliver, deliver);
            deliverList.Insert(~index, deliver);
            this.curCount += deliver.count;
 
            while(this.curCount > this.maxCount)
            {
                if (this.curCount - this.maxCount >= this.deliverList.Last().count)
                {
                    this.curCount -= this.deliverList.Last().count;
                    this.deliverList.Remove(this.deliverList.Last());
                }
 
                else
                {
                    this.deliverList.Last().count -= (this.curCount - this.maxCount);
                    this.curCount -= (this.curCount - this.maxCount);
                }
            }
 
            //현재까지 쌓인 트럭의 택배 출력 부분.
            //Console.WriteLine("stored count : " + this.curCount);
            //this.deliverList.ForEach(x => x.Print());
            //Console.WriteLine();
        }
 
        public void DoDeliver(int curTown)
        {
            while(this.deliverList.Count > 0 && this.deliverList.First().end <= curTown)
            {
                this.curCount -= this.deliverList.First().count;
                this.deliveredCount += this.deliverList.First().count;
                this.deliverList.Remove(this.deliverList.First());
            }
        }
        
    }
 
    class Program
    {
       static void Main(string[] args)
       {
            var input = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList();
            input.Add(int.Parse(Console.ReadLine()));
 
            var truck = new Truck(input[1]);
            var tempList = new List<Deliver>();
 
            for(int i = 0; i < input[2]; i++)
            {
                var inputDeliver = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList();
                var deliver = new Deliver(inputDeliver[0], inputDeliver[1], inputDeliver[2]);
 
                tempList.Add(deliver);
            }
 
            tempList = tempList.OrderBy(x => x.start).ThenBy(x => x.end).ToList();
            tempList.ForEach(x => truck.DeliverProcess(x));
            Console.WriteLine(truck.deliveredCount + truck.curCount);
       }
    }
 
}
 
 
 

 

# 이건 저의 방식 입니다. 다른 분들은 어떻게 했는지 모르겠습니다.

 

저는 시간을 최대한 줄여보려 했는데 그러려면 n^2 을 안써야 겠죠?

BinarySearch를 사용해서 택배가 새로 들어왔을 때 트럭에 있는 리스트에 logN 시간에 넣고

다시 택배 리스트를 관리 했습니다.

 

이 문제를 풀려면 택배를 어떻게 관리할 것인가 정리하는 것이 핵심이 되겠습니다.

처음 입력을 받았을 때는 시작점을 기준으로 정렬해서 가지고 있어야 합니다.

 

4 40

6

3 4 20

1 2 10

1 3 20

1 4 30

2 3 10

2 4 20

 

1 2 10

1 3 20

1 4 30

2 3 10

2 4 20

3 4 20

 

이렇게 정렬해서 메인에서 가지고 있도록 했습니다.

그럼 1번 마을에 도착했을 때, 2번 마을에 도착 했을 때 차례대로

물건을 담아보고 트럭에서 뺄 수 있습니다.

 

트럭에 현재 택배의 리스트를 담고 있습니다.

단 트럭의 택배는 도착점을 기준으로 정렬해서 가지고 있어야 합니다!!!

택배가 트럭에 들어간 순간 어느 마을에서 넣었는지는 전혀 중요하지 않습니다.

내릴 마을이 어디인지를 기준으로 정렬해서 새로운 택배가 들어와도 정렬을

유지해야 합니다.

 

새로운 택배를 만나면 해당 마을에 도착한 것으로 보고

택배 리스트에서 도착점의 택배를 제거해 줍니다.

현재의 택배 갯수와 배달 완료한 택배 갯수를 업데이트 해줍니다.

 

다음 현재 택배를 트럭에 일단 집어 넣습니다.

트럭에 택배가 계속해서 도착점을 기준으로 정렬을 유지하고

있다면 이진 탐색을 이용해 집어넣는 것이 훨씬 빠릅니다!!

 

일단 택배를 집어넣었다면 택배 갯수가 오버 됐을 수 있습니다.

트럭의 택배 리스트의 끝에서 갯수를 빼고 택배의 갯수를

맥스보다 작거나 같도록 유지해 줍니다.

 

마지막 마을까지 택배 집어넣는 것을 완료했다면 트럭에 택배의 갯수가

남아있습니다. 그것을 모두 배달하고 결과를 출력하면 되겠습니다.

 

택배를 집어넣을 때마다 현재 트럭의 택배 리스트를 출력해 봤습니다.

도움이 될지 모르겠습니다.

'C# > 알고리즘' 카테고리의 다른 글

백준# 4963 - 섬의 갯수  (0) 2020.07.28
백준# 1967 - 트리의 지름  (0) 2020.07.28
백준# 10845 - 큐  (0) 2020.06.21
백준 #2504 - 괄호의 값  (0) 2020.06.13
백준 #1343 - 폴리오미노  (0) 2020.05.30

관련글 더보기