[Java/자바 백준 1459] 걷기

풀이

그리디 문제인지만 모든 케이스를 다 고려해주었습니다.

 

헷갈릴 수 있는 상황

-> (0,0) (2,0)  가기

1. 직진해서 2W로 갈 수 있지만, 

2. 0,0 -> 1,1 -> 2,0  이렇게도 갈 수 있습니다 지도가 무한히 크므로

 

다음 케이스별로 모든 조건을 비교해주어서 가장 작은 값을 출력시켰습니다.

 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long X, Y, W, S;
		StringTokenizer st = new StringTokenizer(br.readLine());
		X = Long.parseLong(st.nextToken());
		Y = Long.parseLong(st.nextToken());
		W = Long.parseLong(st.nextToken());
		S = Long.parseLong(st.nextToken());
		
		long min = Long.MAX_VALUE;
		// 가로질러서 가지않고 일자로만 걷기
		min = Math.min(min, W * (X + Y));
		// 가로 지를만큼 지르고 따라서 걷기 
		min = Math.min(min, S * Math.min(X, Y) + W * (Math.abs(X - Y)));
		long tmp;
		
		if((X - Y) % 2 == 0) {
			// 가로지르고 / \ 대각으로 가기 
			tmp = S * Math.min(X, Y) + S * Math.abs(X - Y);
		}
		
		else {
			//대각으로 가다가 마지막만 일자로 가기  
			tmp = S * Math.min(X, Y) + S * (Math.abs(X - Y) - 1) + W;
		}
		min = Math.min(min, tmp);
		System.out.println(min);
	
		
	}

}