[Algorithm] Baekjoon 1459번 : 걷기

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

1459번: 걷기

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    long long dx, dy, w, s;
    cin >> dx >> dy >> w >> s;
 
    long long answer = 0;
    
    if (2 * w <= s) // 2칸이동할 때 대각선이동보다 그냥이동이 더 효율적일 경우
    {
        answer += dy * w + dx * w;
    }
    else // 대각선이동이 더 효율적일 경우
    {
        long long temp = min(dy, dx);
        dy -= temp;
        dx -= temp;
        
        answer += s * temp;
 
        temp = abs(dy - dx); // 일직선 이동량
        
        if (2 * w > 2 * s) // 대각선이 더 효율적이면
        {
            answer += (temp - temp%2) * s + (temp % 2) * w;
        }
        else
        {
            answer += temp * w;
        }
    }
 
    cout << answer;
}

목표지점좌표가 각각 0이상 10억이하라서 완전탐색처럼 코드짜면 아마 시간제한에 걸릴것이다.

 

목표방향으로 1,1만큼 좌표이동을 해야한다고 생각해보자.

1,1만큼 이동하기위해서는 대각선으로 1번이동 한다던가 (1번의 s),  일반이동을 2번 이동해야한다(오른쪽,위. 즉, 2번의 w)

여기서 1번의 대각선이동이 더 효율적이라면 (s < 2 * w) '대각선 이동이 가능한 지점'까지는 대각선으로 이동한다.

여기서 '가능한 지점'이란, 예를들어 목표지점이 3,5이면 3,3까지가 가능한 지점이다.

해당지점까지는 대각선이동을 하는게 무조건적으로 효율적이기 때문에 대각선으로 이동한다.

 

만약 s > 2*w 라면, 즉 1,1을 이동하는데에 대각선이동보다 그냥 일반이동 2번하는게 더 효율적이라면 그냥 목표지점까지 전부 일반이동으로 계산하고 출력해주면 된다.

대각선이 가장 효율적이라 판단될 수 있는 조건에서조차 일반이동이 더 효율적이라면 더이상 대각선이동은 고려할 가치가 전혀 없다.

 

다시 대각선이동이 효율적인 경우로 돌아와보자.

1,1을 이동하는데 대각선이동이 효율적이라 3,3까지는 대각선이동으로 했다.

그런데 나머지 수직or수평인 2칸을 무조건 일반이동으로 해야할까? 

답은 '아니다'이다. 단순히 직선이동을 할 때에도 대각선이동이 가능하다.

 

예시로 0,0에서 2,0을 간다고 가정하면, 오른쪽으로 일반이동을 2번하거나 혹은 대각선이동으로 1,1로 이동했다가 2,0으로 갈 수 있다. 즉 2의배수의 좌표까지는 대각선으로 이동하는것도 '고려'해봐야 한다는 것이다.

이때 각 이동의 가치를 비교할 때는 처음 대각선이동과는 좀 다르게 비교해야 한다.

처음 대각선의 이동은 한번의 대각선이동을 두번의 일반이동과 비교했지만, 현재는 대각선이동과 일반이동의 횟수를 동일하게 비교해야한다. 즉 2 * w와 2 * s를 비교해야 한다. 2,0을 가기위해 일반이동도 2번, 대각선이동도 2번하기 때문이다.