[백준 1459] 걷기 - JAVA

걷기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	2109	410	346	21.899%

문제

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

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

입력

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

출력

첫째 줄에 세준이가 집에가는데 걸리는 최소시간을 출력한다.

예제 입력 1

xxxxxxxxxx
4 2 3 10

예제 출력 1

xxxxxxxxxx
18

 

 

풀이

첫번째, 대각선으로 가지않고 도로를 따라서 가로나 세로로 한 블럭 움직이는게 더 적은 경우.

 

예를들어서 0,0 좌표에서 1,1을 갈 때 대각선으로 가면 1번으로 갈 수 있습니다.

대각선을 사용하지 않는다면 2번에 걸쳐서 1,1에 도착 할 수 있습니다.

 

2*w < s 인 경우 해당됩니다.

 

또 0,0에서 0,2로 가는 경우를 생각해봅시다.

대각선을 이용하지 않고 가면 0,1 0,2 이렇게 2번으로 갈 수 있습니다.

하지만 대각선 2번을 이용해서도 0,0에서 0,2로 갈 수 있습니다

0,0 -> 1,1 -> 0,2

 

이 경우는 2w < 2s 인 경우는 대각선 2개보다 한 블럭씩 움직이는게 최소비용이고

2w > 2s 인 경우는 대각선 2번을 통해서 이동하는게 최소비용입니다.

 

두번째, 대각선으로만 이동 할 경우입니다.

이경우 x==y 일 경우 시작점에서 끝까지 오로지 대각선으로만 이동 할 수 있습니다.

 

마지막으로 대각선으로 이동하고 한 블럭씩 움직이는 것을 둘 다 사용하는 경우입니다.

int 자료형 말고 long으로 해줘야합니다.

 

import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long x,y,w,s;
        
        String [] t = br.readLine().split(" ");
        
        x = Integer.parseInt(t[0]);
        y = Integer.parseInt(t[1]);
        w = Integer.parseInt(t[2]);
        s = Integer.parseInt(t[3]);
        long ans = 0;
        if(2*w < s) {
            ans = (x+y)*w;
        }
        else if(2*w > 2*s) {
            if((x+y)%2==0) {
                ans = Math.max(x, y)*s;
            }
            else {
                ans = (Math.max(x, y)-1)*s;
                ans+=w;
                
            }
        }
        else {
            if(x==y) {
                ans = s*x;
            }
            else {
                ans = Math.min(x*s, y*s);
                ans+=Math.abs(x-y)*w;
            }
        }
        System.out.println(ans);
    }
}
​