[백준 Java]_걷기 (1459)

문제 정보

• 출처 및 난이도: 백준 실버3
• 링크: https://www.acmicpc.net/problem/1459
• 분류: 수학, 조건 분기

---

문제 요약

(0, 0)에서 (X, Y)까지 이동할 때 최소 비용을 구하는 문제.

• 상하좌우 이동: 비용 W
• 대각선 이동: 비용 S (x, y 동시에 ±1)

---

풀이 접근

세 가지 전략의 비용을 각각 계산해서 최솟값 선택

1. 직선만 이동: X + Y번 이동 → (X + Y) * W
2. 대각선 우선 + 직선 보정: 짧은 쪽만큼 대각선, 나머지 직선 → min(X,Y) * S + |X-Y| * W
3. 대각선으로만 커버: 대각선으로 목적지를 덮을 수 있는 경우
   • (X+Y)가 짝수면 대각선 방향을 바꿔가며 max(X,Y) 번에 도달 가능 → max(X,Y) * S
   • 홀수면 1칸 직선 이동 필요 → W + (max(X,Y) - 1) * S

---

핵심 아이디어

• 대각선 이동은 (+1,+1) 뿐 아니라 (+1,-1) 방향도 가능 → X+Y 홀짝에 따라 대각선만으로 도달 가능 여부가 결정됨
  • 짝수: 대각선 방향을 섞어서 max(X,Y) 번에 정확히 도달
  • 홀수: 마지막 1칸은 반드시 직선 필요
• 세 전략 중 최솟값을 출력하면 끝 → 경우의 수가 적어 브루트포스 수준

---

코드

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int X = scanner.nextInt();
        int Y = scanner.nextInt();
        int W = scanner.nextInt();
        int S = scanner.nextInt();


        // 직선
        long way_1 = (long) (X + Y) * W;

        // 대각선 우선 + 직선
        long way_2 = (long) Math.min(X, Y) * S + (long) Math.abs(X - Y) * W;

        // 대각선 2개 +1, + 1 / +1, -1
        // 각각 a, b번 이면 a+b = X, a-b = Y
        long way_3;
        if ((X + Y) % 2 == 0) way_3 = (long) Math.max(X, Y) * S; // 짝수
        else way_3 = W + (long) (Math.max(X, Y) - 1) * S;

        System.out.println(Math.min(Math.min(way_1, way_2), way_3));

        scanner.close();

    }
}

---

배운 점 / 회고

• 대각선이 (+1,-1) 방향도 된다는 걸 처음엔 놓쳤다.
• (X+Y) % 2 홀짝 조건이 핵심인데, 이 조건을 못 잡으면 way_3 계산이 틀린 값이 나온다.
• 이동 횟수가 int 범위를 넘을 수 있어서 long 캐스팅을 계속 했다. (처음부터 long으로 받지...)