[백준]1459번: 걷기

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

1459번: 걷기

---

 

처음에는 dp로 풀려고 했는데, 주어진 정수 범위가 너무 커서 힙 메모리가 부족해서 배열을 만들 수 없었다.

 

그래서 오랫동안 고민하다가 다른 분 풀이를 참고해서 풀었다.

간단하게 생각하면 되는 거였는데 떠오르지가 않아서 오래걸렸따

 

---

 

🐥 조심할 점

 

 - x와 y가 매우 큰 수로 주어지면 연산 결과가 Integer 범위를 초과하기 때문에,

    변수 자료형을 모두 long타입으로 설정해주었다.

 

🐥 풀이

목표지점까지 이동하는 최소 거리 후보로는 다음 3가지가 있다.

(그림 그려서 생각해보면 쉽게 이해가 갈 것이다!!)

 

1️⃣ 직선이동만 하는 경우: (x+y) * w

 

2️⃣ 대각선 이동만 하는 경우

 - 목표 좌표가 (홀수, 홀수) 또는 (짝수, 짝수) 조합인 경우: max(x,y) * s

 - 목표 좌표가 (홀수, 짝수) 또는 (짝수, 홀수) 조합인 경우: (max(x,y)-1) * s

 

3️⃣ 직선 + 대각선 이동 조합: min(x,y) * s + abs(x-y) * w

 

이 중에서 최소값이 정답이다.

 

---

✅ 제출 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] input = reader.readLine().split(" ");
        long x = Integer.parseInt(input[0]);
        long y = Integer.parseInt(input[1]);
        long w = Integer.parseInt(input[2]);
        long s = Integer.parseInt(input[3]);

        long dist1 = (x+y) * w; // 직선 이동 거리
        long dist2; // 대각선 이동 거리
        if ( (x+y)%2 == 1){
            dist2 = (Math.max(x,y)-1) * s + w;
        }else {
            dist2 = Math.max(x,y) * s;
        }
        long dist3 = Math.min(x,y) * s + Math.abs(x-y) * w; // 직선, 대각선 조합 이동 거리

        System.out.println(Math.min(Math.min(dist1, dist2), dist3));
    }
}

 

✅ Reference

 - https://jaewoo2233.tistory.com/36