백준 온라인 저지: 1459 걷기

1459번: 걷기

 

걷기

 

문제

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

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

입력

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

출력

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

 

예제 입력 1

4 2 3 10

예제 출력 1

18

 

 

예외처리만 잘 하면 간단하게 해결할 수 있는 문제이다.

 

크게 다음의 세가지 경우로 나뉜다.

1. S < W (대각선으로 가로지르는 방법이 가로나 세로로 한 블록 건너는 방법보다 빠름.) 

2. W <= S <= W * 2 (가로지르는 방법이 가로나 세로로 두번 건너는 방법보다 빠르거나 같은 시간이 걸림.)

3. S > W * 2 (가로지르는 방법보다 가로나 세로로 두번 건너는 방법이 빠름.)

 

2번과 3번은 크게 문제가 되지 않는다.

2번의 경우에는 가로나 세로로 두번 이동하는 방법보다 대각선으로 한번 이동하는 방법이 시간이 덜 걸리므로,

대각선으로 이동할 수 있을 만큼 이동한 다음에 (min(X, Y) 만큼) 남은 거리를 한 블록씩 건너면 된다.

 

3번의 경우에는 가로지르는 방법보다 한 블록씩 건너는 방법이 더 효율적이므로 목적지까지의 맨해튼 거리에 한 블록을 건너는데 필요한 시간인 S를 곱해주면 된다.

 

이중에 가장 까다로운 경우는 1번인데, 가로지르는 방법이 한 블록씩 건너는 방법보다 항상 빠르므로 다음 사진과 같이 대각선 직선 방향으로 최대한 이동한 다음, 목적지까지 지그재그로 이동한다.

 

이 경우에는 대각선으로 직진한 후 남은 거리(d) 가 짝수이므로 지그재그로 이동하면 문제 없지만, d가 홀수일 때는 지그재그로 이동하면 집에 도착할 수 없으므로, 마지막에 가로지르지 않고 이동해야 한다.

 

아래는 작성한 코드이다.

#include <cstdio>

// 입력
// 첫줄에 X, Y, W, S가 주어진다.
// X: 집이 위치한 X좌표, 0 <= X <= 1,000,000,000
// Y: 집이 위치한 Y좌표, 0 <= Y <= 1,000,000,000
// W: 한 블록 건너는데 필요한 시간, 1 <= W <= 10,000
// S: 대각선으로 한 블록 가로지르는데 필요한 시간, 1 <= S <= 10,000

// 출력
// 세준이가 집에 가는데 필요한 최소 시간을 출력한다.

using ll = long long;

int main()
{
	ll X, Y, W, S;
	scanf("%lld %lld %lld %lld", &X, &Y, &W, &S);

	// sum: 집이 위치한 X좌표와 Y좌표의 합
	// min: 집이 위치한 X좌표와 Y좌표 중 최솟값
 	// max: 집이 위치한 X좌표와 Y좌표 중 최댓값

	ll sum = X + Y;
	ll min = X < Y ? X : Y;
	ll max = sum - min;

	// 대각선으로만 목적지에 도착하는 경우
	if (W > S)
	{		
		// 대각선으로 직진하여 갈수 있는 만큼 이동한 후, 목적지까지 지그재그로 이동한다.
		// 이때 직진이 끝난 후 남은 거리가 홀수면 지그재그로 이동할 수 없다.
		// 따라서 남은 거리 d = max - min 이 홀수면 지그재그로 이동하다가 마지막에 대각선이 아니라 한 블록만 이동한다.
		// 따라서 직선으로 이동한 거리 + 지그재그로 이동한 거리인 max * S에
		// 남은 거리가 홀수인 경우 - S + W를 더하므로
		// (W - S) 에 (max - min) % 2 를 곱한 값을 max * S 에 더한다.

		printf("%lld\n", max * S + (W - S) * ((max - min) % 2));
	}
	// 대각선으로 먼저 이동한 후, 남은 거리를 한 블록 씩 이동하는 경우
	else if (W * 2 >= S)
	{
		printf("%lld\n", min * S + (max - min) * W);
	}
	// 도착할때까지 한 블록씩만 이동하는 경우
	else
	{
		printf("%lld\n", sum * W);
	}
}