[백준] 1459 걷기

문제

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

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

입력

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

출력

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

 

풀이

특별한 알고리즘은 사용하지 않았다. 그냥 생각나는대로 짰다.

1. [대각 이동 시간 > 직선 이동 시간 * 2] 인 경우, 모든 이동은 직선으로만 한다. 따라서 이동 시간은 (X + Y) * W

2. 그렇지 않은 경우, [대각 이동 시간 < 직선 이동 시간]인 경우와 그렇지 않은 경우로 나뉜다.

3. [대각 이동 시간 < 직선 이동 시간]인 경우, 집의 위치가 직선상에 있어도 대각으로 이동한다. 다만 집까지의 거리가 직선 홀수칸이면 대각으로 이동할 수 없기 때문에 , 직선 1칸이 남을 때까지 대각으로 이동한다.

4. 그렇지 않은 경우, 집이 직선상에 있으면 직선으로 이동한다.

 

코드

// CodeTest.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.  
//  

#include <cstdio>
#include <string.h>  
#include <vector>  
#include <algorithm>

using namespace std;  

long long X, Y;
long long orthTime, diagTime;
int main()  
{  
	scanf_s("%d%d%d%d", &X,&Y,&orthTime,&diagTime);
	long long result = 0;
	//대각선 시간 > 직선시간 *2 -> 직선으로만 이동
	//대각선 시간 < 직선시간 *2  -> 집에서 가장 가까운 정사각형까지 대각으로 이동 후 직선이동
	//대각시간 < 직선시간 -> 전부 대각으로만ㅇ ㅣ동
	if (diagTime > orthTime * 2)
	{
		result = (X + Y) * orthTime;
	}
	else
	{
		if (diagTime < orthTime)
		{
			//거리가 홀수면 대각으로만 이동이 불가능하다.
			result = min(X, Y) * diagTime;
			int rest = abs(X - Y);
			if ((rest % 2) == 0)
				result += rest * diagTime;
			else
				result += (rest - 1) * diagTime + orthTime;
		}
		else
		{
			result = min(X, Y) * diagTime + (abs(X - Y) * orthTime);
		}
	}
	printf("%lld", result);
	return 0;
}