[백준 1459번] 걷기 (C++)

문제링크 : https://www.acmicpc.net/problem/1459

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll X, Y, W, S;

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

    cin >> X >> Y >> W >> S;

    ll gap = max(X,Y)-min(X,Y);

    //직선만
    ll tmp1 = (X+Y)*W;

    //대각선 + 직선
    ll tmp2 = min(X,Y)*S + gap*W;

    //대각선만 (대각선만 불가하면 마지막 직선)
    ll tmp3 = gap%2==0 ? (min(X, Y) + gap) * S : (min(X, Y) + gap - 1) * S + W;

    cout << min({tmp1, tmp2, tmp3});

    return 0;
}

 

경우의 수를 먼저 따져 보자.

직선으로만 가능 경우, 대각선과 직선을 섞는 경우, 대각선으로만 가능 경우 이렇게 3가지 케이스가 있다.

먼저 직선으로만 가능 경우를 살펴보면, X축 이동이든 Y축 이동이든 비용이 같기에 총 비용은 (X+Y)*W가 된다.

 

다음으로 대각선과 직선으로 섞는 경우는 우선 갈수 있는 만큼 대각선으로 이동하고, 나머지를 XY이동을 해주면 된다.

따라서 min(X, Y)를 통해 대각선으로 가능한 케이스를 찾고, max(X, Y)-min(X,Y)를 통해 나머지를 판별하고 XY이동을 한다.

마지막으로 대각선으로 이동하는 경우다.

 

이 경우가 살짝 복잡한데, 먼저 대각선으로만 이동하지만 X, Y 값에 따라 온전히 대각선으로만 이동이 불가능한 경우가 있다.

만약 max(X, Y)-min(X,Y)을 2로 나눈 값이 홀수면 온전히 대각선으로만 이동이 불가능하며, 마지막 한번만 X축 이동을 해야한다.

이를 참고하여 계산하면, 우선 대각선으로만 이동가능한 경우는 min(X, Y)를 똑같이 구해주자. 여기에 max(X, Y)-min(X,Y)을 추가로 더하고 S를 곱해준다. 앞서 max(X, Y)-min(X,Y)를 곱한 이유는, 대각선 이동이라는 것이 무조건 우상 방향으로 가는 것이 아닌, 총 4가지 방향으로 갈 수 있기에 먼저 가능한 만큼 우상 방향으로 이동하고 나머지 남은 값에 대해 대각선으로 이리저리 비틀면서 가는 것이다.

비효율적인 것처럼 보일 수 있지만, 비용에 따라 이렇게 이동해도 더 저렴한 케이스가 존재할 수 있다.

그리고 마지막 직선이 필요한 경우는, 단순히 앞서 구한 값에 1을 빼서 S 비용을 곱하고, W 한번 비용을 더해주면 된다.

 

이렇게 구한 3가지 값 중에서 가장 작은 값을 출력하면 되며, 경우에 따라 int 범위를 초과할 수 있기 때문에 long long으로 연산해주어야한다.