[백준 Java]1459_걷기_그리디

🔗 문제링크 🔗

1459번: 걷기

---

🌟 생각 흐름 🌟

완탐으로 한다면 x, y의 범위로 인해서 시간 초과가 날 것 같아 그리디로 풀었다 길을

걷는 경우는 3가지로 나눌 수 있다.

1. 모든 블록을 하나씩 다 걸어가는 방법 
2. 대각선으로 (n, n)까지 가서 (n, m)이나 (m, n)으로 가는 방법 (n이 더 작다고 가정) 
3. 모든 블록을 지그재그로 가는 방법(합이 짝수인 경우에는 모든 경로를 지그재그로 갈 수 있지만 홀수인 경우에는 한 번은 그냥 블록을 걸어가야 한다)

위의 3가지를 계산해서 가장 값이 작은 것을 출력하는 방식으로 제출하였다.

---

🍳 코드 🍳

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

public class boj_1459_걷기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        int endX = Integer.parseInt(st.nextToken());
        int endY = Integer.parseInt(st.nextToken());
        long oneBlockTime = Long.parseLong(st.nextToken());
        long oneCrossTIme = Long.parseLong(st.nextToken());

        int minD = Math.min(endX, endY);
        int maxD = Math.max(endX, endY);
        int totalD = endX + endY;

        //그냥 한 블럭씩 다 걸어가는 경우
        long justOneBlock = totalD * oneBlockTime;
        //(min,min)방향까지 가서 (max,min) or (min,max)남은 거리를 한블럭씩 걸어가는 경우
        long crossAndBlock = minD * oneCrossTIme + oneBlockTime * (maxD - minD);
        //대각선 비용이 더 싼경우 지그재그로 걸어가는 경우 (짝수이면 딱 맞게 갈 수 있지만 홀수이면 한블럭 전까지만 이동하고 걸어간다)
        long zigzag = ((totalD & 1) == 0) ? maxD * oneCrossTIme : (maxD - 1) * oneCrossTIme + oneBlockTime;

        sb.append(Math.min(zigzag, Math.min(justOneBlock, crossAndBlock)));
        System.out.println(sb);
    }
}