Baekjoon 1459 걷기 JAVA

1459번: 걷기

문제

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

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

 

조건

[입력]

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

 

[출력]

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

 

풀이

해당 문제는 도착점 좌표와 상하좌우 이동 값과 대각선 이동 값이 주어졌을 때 0,0에서 도착점까지 최소로 이동 값을 사용하는 최솟값을 구하는 문제다. 요즘 그리디 문제를 풀어보려고 찾아보는 중에 풀어보고자 시도했고 결국 해결하지 못해 구글링의 도움을 받았다.

수학 공부 쫌 해둘걸... 로직은 아래와 같다. 애초에 문제를 보고 int형이 아닌 long을 사용해야 하구나라고 생각했다.

 

1. 입력 처리를 한다.

2. 상하좌우만 사용하여 이동하는 값을 저장한다.

3. 대각선으로 이동하는 값을 저장한다.

    3-1. 좌표값을 더한 게 짝수면 대각선만 사용.

    3-2. 좌표값을 더한 게 홀수면 대각선 사용 + 상하좌우 1개 사용

4. 대각선 + 상하좌우를 사용하여 이동하는 경우를 구한다.

5. 각각 값을 구함과 동시에 최솟값을 경신하고 그 결과를 출력한다.

 

코드

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

public class Main {

	public static void main(String[] args)throws Exception{
		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());
		
		//1. 블록으로 이동하는 경우
		long ans = (x+y)*w;
		
		//2. 대각선으로 이동하는 경우
		if((x+y)%2==0) // 싹다 대각선 이
 			ans = Math.min(ans, Math.max(y, x)*s);
		else // 대각선 이동후 한칸은 블록이
			ans = Math.min(ans, (Math.max(y, x)-1)*s + w);
		
		//3. 대각선 + 블록으로 이동하는 경우
		ans = Math.min(ans, (Math.min(x, y))*s+(Math.abs(x-y))*w);
		
		System.out.println(ans);
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드