[BAEKJOON] 백준 12841: 정보대 등산 (C#)

문제 링크

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

 

 

문제

숭실 대학교 정보 과학관은 숭실 대학교 건물 중 제일 높은 곳에 있다. 민주는 평소에 버스를 타고 이 언덕을 오르지만, 이 문제에 등장하기 위하여 오늘 하루만 걸어서 올라간다. 정보 과학관을 오르는 길은 왼쪽 길과 오른쪽 길이 있다. 민주는 처음에 왼쪽 길 맨 아래에 있고 정보 과학관을 오른쪽 길 맨 위에 있다. 정보 과학관을 오르는 길은 매우 구불구불하다. 또, 길의 중간 중간에는 횡단보도가 있다. 민주는 횡단보도를 한번만 건널 수 있다. 최소한으로 걷기 위해서 민주가 건너야 하는 횡단 보도의 번호와 걸어야 할 거리를 구해 더운 여름 민주를 도와주자!

 

 

입력

첫 번째 줄에는 지점의 개수 n 이 주어진다. (2 ≤ n ≤ 100,000)

횡단보도는 1번 지점부터 n 번 지점까지 한 개 씩 있고, 왼쪽 1번 지점에는 민주가, 오른쪽 n 번 지점에는 정보 과학관이 위치한다.

• 다음 줄에는 i 번째 지점에 있는 횡단보도의 거리 (0 < cross ≤ 100,000) 가 주어진다. (1 ≤ i ≤ n)
• 다음 줄에는 i 번째 지점에서 i+1번째 지점까지 왼쪽 길의 거리 (0 < left ≤ 100,000) 가 주어진다. (1 ≤ i ≤ n-1)
• 다음 줄에는 i 번째 지점에서 i+1번째 지점까지 오른쪽 길의 거리(0 < right ≤ 100,000) 가 주어진다. (1 ≤ i ≤ n-1)

 

 

출력

민주가 최소 길로 가기 위해 건널 횡단보도는 몇 번째 지점에 있는지 출력하고, 민주가 최소 길로 가기 위해 걸어야 하는 거리를 출력한다.

만약, 최소 거리로 갈 수 있는 지점이 여러곳이라면 번호가 낮은 지점을 출력한다.

 

 

 

통과한 답안

namespace _12841
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            long[] cross = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
            long[] left = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
            long[] right = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();

            long[] leftSum = new long[n];
            long[] rightSum = new long[n];

            for (int i = 1; i < n; i++)
            {
                leftSum[i] = leftSum[i - 1] + left[i - 1];
            }

            rightSum[0] = right.Sum();
            for (int i = 1; i < n; i++)
            {
                rightSum[i] = rightSum[i - 1] - right[i - 1];
            }

            long minDistance = long.MaxValue;
            int crossIdx = -1;

            for (int i = 0; i < n; i++)
            {
                long totalDistance = leftSum[i] + cross[i] + rightSum[i];
                if (totalDistance < minDistance)
                {
                    minDistance = totalDistance;
                    crossIdx = i + 1;
                }
            }

            Console.WriteLine($"{crossIdx} {minDistance}");
        }
    }
}

 

출발점에서 목적지 가는데 가장 짧은 거리를 구하는 문제인데,

출발점은 왼쪽 아래, 목적지는 오른쪽 위에 있어서 횡단보도를 건너야 하는데,

횡단보드는 1번만 건널 수 있는 조건이 있는 문제이다.

 

따라서 이 문제를 해결할 로직은

각각의 횡단보도를 건너는 거리를 구해서 그 중에서 최소의 거리를 이용하는 것이다.

이를 위해서 횡단보도를 건너기 전의 이동 거리 leftSum[i]와

횡단보도의 이동 거리 cross[i]와 횡단보도를 건넌 후의 이동거리 rightSum[i]를 이용하였다.

 

leftSum의 경우에는 왼쪽길의 거리들을 이용하여 해당 위치까지의 합으로,

rightSum의 경우에는 이와 반대되는 방향이므로 rightSum[0]은 right의 Sum으로 구하고

그 이후에는 rightSum[1] = rightSum[0] - right[0]의 방식으로 구하였다.

 

이들을 구한 후에는 n개의 횡단보도를 순회하면서

총 이동거리(왼쪽 길 + 횡단보도 + 오른쪽 길)를 구해서

최소 이동거리와 비교하여 더 작은 값을 선택하도록 구현하였다.

 

코드를 구현하는데 있어서 실수할 수 있는 부분들이 존재했던 문제로

처음으로는 leftSum과 rightSum의 방향이 반대인 점을 실수할 수 있는 것과

문제 자체에는 int로 구할 수 있을 것 같은 범위이지만,

rightSum[0]을 구하는 과정에서 right.Sum()함수를 사용하는 과정에서

100,000이 100,000개 있는 경우라면 long을 이용해야되는 점이 있었다.