[BAEKJOON] 백준 1678: 기차 (C#)

문제 링크

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

 

 

문제

사무실에서 가까스로 도망친(장애물이 계단을 막고 있는 입력이 주어졌다) 이 사장은 기차를 이용하여 멀리 도망치기로 결심하였다. 도망을 치는 도중에 한 기차를 오래 타고 있는 것은 위험했기 때문에, 이 사장은 같은 기차를 타고 두 역 이상을 이동하지 않기로 하였다. 기차의 종류가 같더라도 출발 시간이 다르면 같은 기차가 아니다.

모든 기차는 0번 역에서 각 기차의 고유 출발시간에 매 시간마다 계속 출발한다. 이 사장은 0번 역에서 한 기차를 타고 1번 역에서 내린다. 그리고 1번 역에서 기차를 기다리다 가장 먼저 오는 기차를 타고 2번 역으로 이동한다. 그리고 2번 역에서 가장 먼저 도착한 기차를 타고 3번 역으로 이동하며, 이를 N번 역에 도착할 때까지 반복한다.

이와 같이 N번 역으로 이동했을 때, 가장 마지막에 탄 기차의 번호를 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 기차의 종류 개수 T(<30), 이 사장이 출발하는 시간(분 단위로) M(<60), N(<1,000,000,000)이 주어진다. 다음 줄에는 각 기차 종류별로 기차의 번호(길이 10을 넘지 않는 문자열)과 그 기차가 0번 역에서 출발하는 시간을 분 단위(<60)로 입력한다. 각 줄의 끝에는 -1로 주어진다. 같은 시간에 출발하는 기차는 없다고 가정해도 좋다.

 

 

출력

첫째 줄에 기차의 번호를 출력한다.

 

 

 

통과한 답안

namespace _1678
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int T = int.Parse(inputs[0]);
            int M = int.Parse(inputs[1]);
            int N = int.Parse(inputs[2]);

            List<(string trainNumber, int departureTime)> allTrains = new List<(string trainNumber, int departureTime)>();
            for (int i = 0; i < T; i++)
            {
                string[] trainInfo = Console.ReadLine().Split(' ');
                string trainNumber = trainInfo[0];
                for (int j = 1; j < trainInfo.Length - 1; j++)
                {
                    int departureTime = int.Parse(trainInfo[j]);
                    allTrains.Add((trainNumber, departureTime));
                }
            }

            allTrains.Sort((a, b) => a.departureTime.CompareTo(b.departureTime));

            int startIdx = -1;
            for (int i = 0; i < allTrains.Count; i++)
            {
                if (allTrains[i].departureTime >= M)
                {
                    startIdx = i;
                    break;
                }
            }

            if (startIdx == -1)
            {
                startIdx = 0;
            }

            int lastIdx = (startIdx + N - 1) % allTrains.Count;
            string lastTrain = allTrains[lastIdx].trainNumber;

            Console.WriteLine(lastTrain);
        }
    }
}

 

문제의 설명과 예제가 좋지 않은 문제이다.

이 사장이라는 사람이 N번째 있는 역까지 이동하려고 하는데,

한 번 탄 기차는 다음 역에서 내려야 한다는 조건이 달려있다.

기차의 종류는 T개 있으며, 각각의 기차에 여러 대의 기차가 다른 출발 시간을 가진다.

 

입력은

첫째 줄에 기차의 종류 T, 이 사장의 출발 시간 M, 도착할 역의 번호 N 이 주어지고,

둘째 줄부터 T + 1번째 줄까지 각각 기차의 출발 시간들이 주어진다.

 

예를 들어서 예제 1번과 같이

2 48 783
11 10 20 30 -1
13-4 16 25 35 45 58 -1

라고 주어지면

기차의 종류는 T개가 있으며, 이 사장이 출발하는 시간은 48분이고 783번 역까지 가야 한다.

이 때, 11이라는 기차는 매 시 10, 20, 30분에 출발하고

13-4라는 기차는 매 시 16, 25, 35, 45, 58분에 출발한다.

 

N 값의 범위가 1,000,000,000 미만으로 모든 루트를 찾는 것은 시간 초과가 발생하므로,

기차를 타는 방식을 이해해야되는 문제이다.

 

우선 조건에 나와있지 않지만,

0번 역에서 1번 역으로 가는 시간, x번 역에서 x + 1번 역으로 가는 시간은

모든 기차가 동일하다고 가정해야지 문제를 풀 수 있다.

 

따라서 위의 예제 1번을 가져와서 살펴보면,

처음에 이 사장이 타는 기차는

58분에 출발하는 13-4번 기차 이고 이를 타고 1번 역까지 간다.

그 이후에 시간은 알 수 없지만, 2번 역까지 가기 위해 기차를 타는데

이 기차는 11번 기차 의 10분 출발 기차 이다.

(이 조건은 문제에 적혀있지 않으며 유추해야 되는 부분으로,

기차 마다 역에 도착하는 시간이 다르다면 문제를 해결할 수 없다)

 

이 11번 기차의 10분 출발 기차를 타고 2번 역까지 간 후에는

13-4번 기차의 16분 출발 기차를, 그 다음은 11번 기차의 13-4분 출발 기차를,...

 

의 방식으로 모든 기차의 출발 시간을 하나의 리스트로 모은 후에

지금 타고 있는 기차의 출발 시간보다 하나 다음 기차를 타는 방식으로 진행된다.

 

즉, 도착해야될 역 N이 주어졌을 때,

모든 기차의 출발 시간을 하나의 리스트로 모은 다음,

처음 타는 기차의 인덱스를 이용하여 문제를 해결할 수 있다.

int lastIdx = (startIdx + N - 1) % allTrains.Count;
string lastTrain = allTrains[lastIdx].trainNumber;

 

이 때, 주의해야되는 부분은 처음 탄 기차는 1번 역까지,

2번째 타는 기차는 2번 역까지, ... n번째 타는 기차는 n번 역까지 이동하므로

마지막에 타는 기차는 처음 인덱스 + N - 1번째 기차가 된다.

이를 모든 기차의 대수로 나누면 마지막에 타는 기차의 인덱스를 알 수 있다.

 

 

문제 자체는 어렵지 않으나,

N 값이 크기 때문에 모든 기차를 순회하는 것은 불가능하고

기차를 타는 방식도 정확하게 표기되어 있지 않기 때문에

풀이하는 사람의 재량으로 판단해야되는 부분이 있는 좋지 않은 문제라고 생각한다.