[백준 - C#] 14469번 소가 길을 건너간 이유 3

문제링크

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

14469번: 소가 길을 건너간 이유 3

 

문제

이웃 농장의 소가 길을 마구잡이로 건너는 것에 진절머리가 난 존은 극단의 결정을 내린다.
농장 둘레에 매우 큰 울타리를 짓는 것이다. 이렇게 하면 근처 농장 출신의 소가 들어올 일이 거의 없다.
이 일로 주변 소들이 분개하였다. 친구네 집에 놀러 갈 수 없을 뿐만 아니라, 매년 참가하던 국제 젖 짜기 올림피아드에도 올해는 참가할 수 없게 되었기 때문이다.

이웃 농장의 소 중 존의 농장에 방문할 수 있는 소가 조금 있긴 하지만, 그들도 안심할 수 있는 건 아니다.
존의 농장에 들어가는 문은 하나밖에 없고, 그 문을 통과하려면 감시관의 길고 긴 검문을 받아야 한다.
여러 마리의 소가 한 번에 들어가려고 하면 줄이 그 만큼 길어진다.

N마리의 소가 이 농장에 방문하러 왔다. 소가 도착한 시간과 검문받는 데 걸리는 시간은 소마다 다르다. (물론 같을 수도 있다.) 두 소가 동시에 검문을 받을 수는 없다.
예를 들어, 한 소가 5초에 도착했고 7초 동안 검문을 받으면, 8초에 도착한 그 다음 소는 12초까지 줄을 서야 검문을 받을 수 있다.
모든 소가 농장에 입장하려면 얼마나 걸리는 지 구해보자.

조건

시간제한 : 2초
메모리 제한 : 512 MB

입력

첫 줄에 100 이하의 양의 정수 N이 주어진다.
다음 N줄에는 한 줄에 하나씩 소의 도착 시각과 검문 시간이 주어진다.
각각 1,000,000 이하의 양의 정수이다.

출력

모든 소가 농장에 입장하는 데 걸리는 최소 시간을 출력한다.

 

문제정리

1. 소는 한마리씩 검문을 받을 수 있다
2. 하나의 소는 도착시간과 검문 시간이 주어진다
3. 모든 소가 농장에 입장하려면 걸리는 최소 시간을 구하자

이번 문제의 경우 모든 소가 한마리씩 농장에 입장하는 최소 시간을 구하는 문제입니다.

모든 소가 최소시간으로 들어가려면 검문소에 빨리 도착한 소부터 빨리 빨리 넣으면 될 것 같습니다.

그러므로 일단 입력 받은 도착 시간과 검문시간 중 도착 시간으로 오름차순 정렬 하였습니다

 

그다음 첫번째는 대기 시간이 없기 때문에 도착 시간과 검문이 걸리는 시간을 더해주어 최소 시간으로 잡고, 반복문을 두번째 소부터 진행하여 정해진 규칙으로 시간을 계산하였습니다.

 

규칙으로는 총 걸린 시간보다 도착시간이 크다면 기다림 없이 바로 검문 받으면 되기 때문에 최소 시간을 도착 시간과 검문이 걸리는 시간을 더하여 넣어줍니다.

만약 기다림이 있다면 최소 시간에 검문이 걸리는 시간을 더 더해주었습니다.

 

아래의 코드에 주석과 코드를 살펴보면 쉽게 이해 할 수 있습니다.

C# 코드

static void Main(string[] args)
{
    // 14469
    StreamWriter writer = new StreamWriter(OpenStandardOutput());
    StreamReader reader = new StreamReader(OpenStandardInput());
 
    int N = int.Parse(reader.ReadLine());
    List<(int, int)> cows = new List<(int, int)>();
 
    for (int i = 0; i < N; i++)
    {
        string[] input = reader.ReadLine().Split();
        cows.Add((int.Parse(input[0]), int.Parse(input[1]))); // 도착시간과 검문시간 입력
    }
 
    cows = cows.OrderBy(time => time.Item1).ToList(); // 도착시간을 가지고 오름차순 정렬
    int minTime = cows[0].Item1 + cows[0].Item2; // 처음값은 대기시간이 없으므로 바로 입력
 
    for (int i = 1; i < N; i++)
    {
        if (minTime <= cows[i].Item1) // 기다리는 시간이 없으면 도착시간 + 검문시간
            minTime = cows[i].Item1 + cows[i].Item2;
        else // 기다리는 시간이 있기 때문에 기다린시간 + 검문시간
            minTime += cows[i].Item2;
    }
 
    writer.WriteLine(minTime);
 
    writer.Close();
    reader.Close();
}

 

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.