2024. 6. 6. 00:08ㆍIT/BaekJoon
문제 링크
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을 이용해야되는 점이 있었다.
'IT > BaekJoon' 카테고리의 다른 글
[BAEKJOON] 백준 2979: 트럭 주차 (C#) (0) | 2024.06.07 |
---|---|
[BAEKJOON] 백준 2909: 캔디 구매 (C#) (0) | 2024.06.06 |
[BAEKJOON] 백준 17626: Four Squares (C#) (1) | 2024.06.05 |
[BAEKJOON] 백준 10610: 30 (C#) (0) | 2024.06.05 |
[BAEKJOON] 백준 28238: 정보 선생님의 야망 (C#) (1) | 2024.06.05 |