BOJ 1459 걷기

문제 풀이의 핵심은 한블럭 이동을 w 대각선 이동을 s라 할때 (0,0) 에서 (1,1)로 갈수 있는 방법중 최소시간을 우리는 구할 수 있다. 즉 s 와 2*w 중 걸리는 시간이 작은 것을 고르면 된다. 

 

단순하게 생각하면 만약 대각선으로 움직이는 것이 직선으로 이동하는것보다 작을 경우 즉 s<2*w 일때 무조건 대각선으로 움직이는게 유리하다. 따라서 x,y 에서 한쪽 방향 대각선으로 최대로 내려갈수 있는 범위는 x,y 중 작은 값 까지 내려갈수 있다. 

 

여기서 생각할 부분이 있다. 만약 |x-y| 가 2의 배수라면 w,s 중 작은 길을 택하면 된다.

예시로 입력이 2 0 12 10 일때 w=12, s=10 이고 (2,0)으로 갈수있는 최소시간은 20이 된다. 이유는 w를 이용하여 (1,0), (2,0) 이동하는 방법 하나와, s를 이용하여 (1,1), (2,0) 이동하는 방법이 있기 때문이다.

 

하지만, 만약 |x-y| 가 2의 배수가 아니라면 최대로 갈수 있는 2의 배수를 찾고 나머지는 1번은 대각선으로 움직일 수 없으므로 무조건 w로 이동을 해야한다.

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	long long x, y;
	int w, s;

	long long ans = 0;

	cin >> x >> y >> w >> s;

	if(2 * w <= s)
	{
		ans += (x + y)*w;
	}
	else
	{
		if(x <= y)
		{
			ans += x * s;
			if((y - x) % 2 == 0)
			{
				if(w <= s)
				{
					ans += (y - x)*w;
				}
				else
				{
					ans += (y - x)*s;
				}
			}
			else
			{
				int remainder = (y - x) % 2;
				if(w <= s)
				{
					ans += (y - x)*w;
				}
				else
				{
					ans += ((y - x) - remainder)*s + remainder * w;
				}
			}
			
		}
		else
		{
			ans += y * s;
			if((x - y) % 2 == 0)
			{
				if(w <= s)
				{
					ans += (x - y)*w;
				}
				else
				{
					ans += (x - y)*s;
				}
			}
			else
			{
				int remainder = (x - y) % 2;
				if(w <= s)
				{
					ans += (x - y)*w;
				}
				else
				{
					ans += ((x - y) - remainder)*s + remainder * w;
				}
			}
		}
	}
	cout << ans;
}