걷기


작성일 : 2017-01-30 22:45:05
조회수 : 495



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


$(0,0)$ 에서 시작하여 가로, 또는 세로로 한 칸을 이동하거나 대각선으로 가로질러 이동할 수 있는 2가지 경우가 있는 상황입니다. 이 상황에서 최선의 방법을 찾기 위해 선택할 수 있는 방법은 3가지가 있습니다.


1. 가로, 또는 세로로만 이동하여 목적지에 도달한다.

2. 대각선으로만 이동하여 목적지에 도달한다.

3. 두 방법을 섞어 이동한다.

위의 3가지 방법을 직접 적용하여 최솟값을 찾으면 됩니다. 이 때 유의해야 할 점이 있는데, 대각선으로만 이동하는 경우에는 두 점의 합이 반드시 짝수인 지점만 가능하다는 것입니다. 왜냐하면, $(0,0)$ 지점에서 x축과 y축의 방향으로 절대값이 1씩 변화하기 때문입니다. 그러므로 목표 좌표의 두 점의 합이 홀수일 경우, 대각선으로만 이동하는 것은 불가능하므로 대각선으로 도착 지점 직전까지 도착한 후, 직선으로 1칸을 이동해야 합니다.

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

int main()
{
    long long x, y, w, s, ans, mod;

    cin >> x >> y >> w >> s;
    if (x > y) swap(x, y);
    mod = (y - x) % 2LL;
    ans = (x + y)*w;
    ans = min(ans, (y - mod)*s + mod*w);
    ans = min(ans, x*s + (y - x)* w);
    cout << ans;
}

걷기 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글