백준 No.1459 걷기 - JAVA

 

 

 

문제

세준이는 학교에서 집으로 가려고 한다. 도시의 크기는 무한대이고, 도시의 세로 도로는 모든 정수 x좌표마다 있고, 가로 도로는 모든 정수 y좌표마다 있다. 세준이는 현재 (0,0)에 있다. 그리고 (X,Y)에 위치한 집으로 가려고 한다. 세준이가 걸을 수 있는 방법은 두가지 인데. 하나는 도로를 따라서 가로나 세로로 한 블록 움직여서 이번 사거리에서 저 사거리로 움직이는 방법이고, 블록을 대각선으로 가로지르는 방법이 있다. 

세준이가 집으로 가는데 걸리는 최소 시간을 구하는 프로그램을 작성하시오

 

입력

첫째 줄에 집의 위치 X Y 와 걸어서 한 블록 가는데 걸리는 시간 W와 대각선으로 한 블록을 가로지르는 시간 S가 주어진다. X와 Y는 1,000,000,000보다 작거나 같은 음이 아닌 정수이고, W와 S는 10,000보다 작거나 같은 자연수이다.

 

 

 

총 4가지의 경우의 수가 있음

 

1번 평행이동만 했을 경우(W는 한 블록을 가는데 걸리는 시간) 총 6개의 블록을 갔으니 6 * w

 

2번 대각선으로만 이동하는데 두 좌표의 합이 짝수 인경우(s는 한 대각선을 가는데 걸리는 시간)

 

3번 대각선으로만 이동하는데 두 좌표의 합이 홀수 인 경우(s는 한 대각석을 가는데 걸리는 시간)

   마지막 대각선을 평행이동으로 이동하면서 둘 중 큰 값에서 -1 하고 플러스 평행이동 1 한다.

 

4번 대각선으로 갈 만큼 가고 나머지는 평행이동으로 갈 때

 

     이 경우는 x,y좌표 둘 중 작은 값을 선택해서 먼저 간다( 큰 값을 고를 경우 원하는 좌표 그 이상을 가버릴 수도 있다)

     그리고 나머지는 x-y 절댓값을 통해 대각선으로 얼마만큼 이동하고 원하는 좌표까지 얼마나 남았는지 알 수 있다. 

     이 절댓값을 더해주면 된다. 

 

 

4가지 경우 중 제일 작은 값을 찾아 출력하면 정답이다.

 

코드

 

package com.example.algorithgm.today;

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

public class Work {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        long x=Long.parseLong(st.nextToken());
        long y=Long.parseLong(st.nextToken());
        long w=Long.parseLong(st.nextToken());  //평행이동시간
        long s=Long.parseLong(st.nextToken());  //대각선이동시간

        long temp1,temp2,temp3;

        //1. 평행이동만 할떄
         temp1 = (x+y) * w;


        temp2 = 0;
        //
        if((x+y) % 2 == 0){
                temp2 = Math.max(x,y) * s;
        }else{
            temp2 = (Math.max(x,y) - 1) * s + w;
        }

        temp3 = (Math.min(x, y))*s+(Math.abs(x-y))*w;

        System.out.println(Math.min(temp1, Math.min(temp2, temp3)));
    }
}

 

 

참고

https://velog.io/@ehdcks3421/%EB%B0%B1%EC%A4%80-%EA%B1%B7%EA%B8%B0-1459

[백준] 걷기-1459