문제 출처

1. 문제설명

• 입력
  • 크기 X, Y,
  • 상하좌우로 가는데 걸리는 시간 W
  • 대각선으로 가로지르는 시간 S
• (X, Y)까지의 최소 시간 출력

2. 알고리즘 설계

• 언급할 내용은 다른 블로그를 참고했음을 밝힘.
• 경우의 수
  • 수평으로만 이동
  • 대각선으로만 이동
    • X+Y % 2 == 0
    • Else
  • 대각선+수평 이동

3. 로직

• 경우의 수
  • 수평으로만 이동
    • (X+Y) * W
  • 대각선으로만 이동
    • X+Y % 2 == 0
      • 이 부분의 접근이 정말 신기했다.
        • 최단 거리를 구하는 BFS는 이동을 한 칸으로 치는데
        • 이 문제는 한 칸 안에서 대각선으로 이동하는 것이다.
      • max(X,Y) * S
    • Else
      • 홀수라면, 대각선만을 사용해서 이동할 수 없다.
      • 마지막 칸은 수평으로 이동해야 함.
      • 큰 값에서 이동 1회를 빼주면 된다.
      • (max(X,Y)-1) * S + W
  • 대각선+수평 이동
    • X, Y 중 작은 값만큼 대각선 이동
    • 나머지 수평 이동
    • min(X,Y)*S + abs(X-Y)*W

4. 전체 코드

#include <iostream>
using namespace std;
using ll = long long;

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

    ll x, y, w, s;
    cin >> x >> y >> w >> s;

    ll c1 = (x + y) * w;
    ll c2 = (x + y) % 2 == 0 ? (max(x, y) * s) : ((max(x, y) - 1) * s + w);
    ll c3 = min(x, y) * s + abs(x - y) * w;

    cout << min(c1, min(c2, c3));
    return 0;
}

5. 소감

• 평소 BFS 풀이에 너무 익숙해진 나머지…
  • 1칸 이동으로 생각해버린 게 문제였다.
• 문제를 직접 시뮬레이션 해보고 구현해보는 습관을 길러야겠다.