[BAEKJOON] 백준 1459: 걷기 (C#)

문제 링크

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

 

 

문제

세준이는 학교에서 집으로 가려고 한다. 도시의 크기는 무한대이고, 도시의 세로 도로는 모든 정수 x좌표마다 있고, 가로 도로는 모든 정수 y좌표마다 있다. 세준이는 현재 (0, 0)에 있다. 그리고 (X, Y)에 위치한 집으로 가려고 한다. 세준이가 걸을 수 있는 방법은 두가지 인데, 하나는 도로를 따라서 가로나 세로로 한 블록 움직여서 이번 사거리에서 저 사거리로 움직이는 방법이고, 블록을 대각선으로 가로지르는 방법이 있다.

세준이가 집으로 가는데 걸리는 최소시간을 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 집의 위치 X Y와 걸어서 한 블록 가는데 걸리는 시간 W와 대각선으로 한 블록을 가로지르는 시간 S가 주어진다. X와 Y는 1,000,000,000보다 작거나 같은 음이 아닌 정수이고, W와 S는 10,000보다 작거나 같은 자연수이다.

 

 

출력

첫째 줄에 세준이가 집에가는데 걸리는 최소시간을 출력한다.

 

 

 

통과한 답안

namespace _1459
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            long X = long.Parse(inputs[0]);
            long Y = long.Parse(inputs[1]);
            long W = long.Parse(inputs[2]);
            long S = long.Parse(inputs[3]);

            long time1 = (X + Y) * W;
            long time2 = Math.Min(X, Y) * S + Math.Abs(X - Y) * W;
            long time3 = 0;

            if ((X + Y) % 2 == 0)
            {
                time3 = Math.Max(X, Y) * S;
            }
            else
            {
                time3 = (Math.Max(X, Y) - 1) * S + W;
            }

            long answer = Math.Min(time1, Math.Min(time2, time3));
            Console.WriteLine(answer);
        }
    }
}

 

이동해야할 (X, Y) 좌표가 주어지고

x축으로 1칸 혹은 y축으로 1칸 이동하는 시간은 W,

x, y축으로 동시에 1칸 이동(대각선 이동)하는 시간은 S로 주어진 경우

(0, 0)에서 (X, Y)까지 이동하는 최소 시간을 구하는 문제이다.

 

처음에는 각각의 경우(W와 S를 비교하고, X + Y의 값이 짝수인지 홀수인지 등)를

나눠서 if문을 이용하여 최소 시간을 구하도록 구현하였으나

분기를 나누는 과정에서 누락되는 등의 문제가 생기는 이슈가 있었다.

 

따라서 각각의 분기를 나누지 않고,

발생하는 경우에 필요한 시간들을 모두 구한 뒤에

이들 중에서 최솟값을 구하는 방식으로 문제를 해결하였다.

 

이동하는 방법의 수는 총 3가지로 나눌 수 있는데,

1. 가로 혹은 세로로만 이동하는 경우

2. 대각선을 최소한 이용하고 남은 거리를 가로 혹은 세로로 이동하는 경우

3. 대각선을 최대한 이용하고 남은 거리를 가로 혹은 세로로 이동하는 경우

 

time1은 1번의 경우를 구현한 것으로 X와 Y를 더한 뒤에 W를 곱하여 구했다.

 

time2는 2번의 경우를 구현한 것으로 X와 Y중의 작은 값에 대해 대각선으로 이동하고

남은 거리를 가로 혹은 세로로 이동하도록 구현하였다.

 

time3은 3번의 경우를 구현한 것으로 X + Y가 짝수라면 둘 중 큰 값만큼 대각선으로 이동하고

홀수라면 둘 중 큰 값에서 1을 뺀만큼 대각선으로 이동하고

1칸 가로 혹은 세로로 이동하게 구현하였다.

 

이렇게 각각의 경우에 필요한 시간들을 모두 구한 뒤에

이들 중에서 가장 작은 값을 선택하도록 구현하여서

많은 분기에 대해서 if문을 사용하지 않고 문제를 해결할 수 있었다.