음하철도 구구팔 (백준 1393번) [JAVA]

문제 링크 : www.acmicpc.net/problem/1393

1393번: 음하철도 구구팔

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128 MB	568	96	86	29.153%

최백준은 음하철도 구구팔에 탔다.

문제는 구구팔의 기장인 조교 김재홍이 반쯤 미쳐서 열차를 멈추지 않는다는 것이다. 그래서 최백준은 달리고 있는 열차에서 뛰어내려야 한다.

그런데 뛰어내릴 때 정류장 까지 거리가 너무 멀면 마이 아플 수 있다.

그래서 철도가 정류장에 가장 많이 근접했을 때 뛰어내리고자 한다.

어디서 뛰어내려야 하는가?

입력

첫째 줄에는 정류장의 위치 x y가 주어지고, 둘째 줄에는 현재 열차의 위치 X Y와 열차가 초마다 이동하는 x좌표 y좌표가 주어진다. 열차는 항상 직선으로 움직인다.

주어지는 모든 수는 -100이상, 100이하의 정수이다.

출력

최백준이 뛰어내리는 위치를 출력한다. 정답은 항상 정수이다.

 

풀이

수학적으로, 시작점에서 x,y초당 이동비율을 통해 일차방정식을 만들고,

정류장을 지나며 기차 방정식에 수직인 방정식을 세운 뒤, 교점을 찾았을때가 정류장과의 최소거리이다.

하지만 정답은 정수밖에 안되기 때문에, 정수이면서 처음 일차방정식에 해당하는 값을 찾아야 한다.

그래서 계산하는게 아니라 모든 정수들을 대입했을때의 최소값을 찾는것으로 했다.

 

코딩

public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    public static void main(String[] args)throws Exception {
    	String[] stl = br.readLine().trim().split(" ");
    	int path[][] = new int[202][202];
    	int stopx = Integer.parseInt(stl[0]);
    	int stopy = Integer.parseInt(stl[1]);
    	
    	stl = br.readLine().trim().split(" ");
    	
    	int intx = Integer.parseInt(stl[0]);
    	int inty = Integer.parseInt(stl[1]);
    	int secx = Integer.parseInt(stl[2]);
    	int secy = Integer.parseInt(stl[3]);
    	
    	//배열 초기화
    	for(int i = 0; i<=200; i++) {
    		for(int j = 0; j<=200; j++) {
    			path[i][j] = 99999;
    		}
    	}
    	
    	//멈춰있는 기차
    	if(secx == 0 && secy ==0) {
    		System.out.println(intx +" "+ inty);
			return;
    	}
    	
    	
    	//x,y가 고정일때 처리
    	if(secx == 0) {
    		if(secy > 0) {
    			if(inty > stopy) {
        			System.out.println(intx +" "+ inty);
        			return;
        		}
        		else {
        			System.out.println(intx+" "+ stopy);
        			return;
        		}
    		}
    		else {
    			if(inty < stopy) {
        			System.out.println(intx +" "+ inty);
        			return;
        		}
        		else {
        			System.out.println(intx+" "+ stopy);
        			return;
        		}
    		}
    		
    	}
    	
    	if(secy == 0) {
    		if(secx > 0) {
    			if(intx > stopx) {
        			System.out.println(intx +" "+inty);
        			return;
        		}
        		else {
        			System.out.println(stopx+" "+inty);
        			return;
        		}
    		}
    		else {
    			if(intx < stopx) {
        			System.out.println(intx +" "+inty);
        			return;
        		}
        		else {
        			System.out.println(stopx+" "+inty);
        			return;
        		}
    		}
    		
    	}
    	
    	int distancex;
    	int distancey;
    	
    	//1사분면
    	if(secx>0 && secy >0) {
    		for(int x = intx; x<=100; x++) {
    			for(int y = inty; y<=100; y++) {
    				//정수인 점
    				if(secx*y-secx*inty == secy*x-secy*intx) {
    					distancex = stopx-x;
    					distancey = stopy-y;
    					path[x+100][y+100] = distancex*distancex + distancey*distancey;
    				}
    			}
    		}
    	}
    	//2사분면
    	else if(secx>0 && secy<0) {
    		for(int x = intx; x<=100; x++) {
    			for(int y = inty; y>=-100; y--) {
    				//정수인 점
    				if(secx*y-secx*inty == secy*x-secy*intx) {
    					distancex = stopx-x;
    					distancey = stopy-y;
    					path[x+100][y+100] = distancex*distancex + distancey*distancey;
    				}
    			}
    		}
    	}
    	//3사분면
    	else if(secx <0 && secy <0) {
    		for(int x = intx; x>=-100; x--) {
    			for(int y = inty; y>=-100; y--) {
    				//정수인 점
    				if(secx*y-secx*inty == secy*x-secy*intx) {
    					distancex = stopx-x;
    					distancey = stopy-y;
    					path[x+100][y+100] = distancex*distancex + distancey*distancey;
    				}
    			}
    		}
    	}
    	//4사분면
    	else if(secx<0 && secy>0) {
    		for(int x = intx; x>=-100; x--) {
    			for(int y = inty; y<=100; y++) {
    				//정수인 점
    				if(secx*y-secx*inty == secy*x-secy*intx) {
    					distancex = stopx-x;
    					distancey = stopy-y;
    					path[x+100][y+100] = distancex*distancex + distancey*distancey;
    				}
    			}
    		}
    	}

    	
    	int ansx = 0;
    	int ansy = 0;
    	int anspath = 99999;
    	

    	for(int i = 0; i<=200; i++) {
    		for(int j = 0; j<=200; j++) {
    			if(anspath > path[i][j]) {
    				ansx = i - 100;
    				ansy = j - 100;
    				anspath = path[i][j];
    			}
    		}
    	}
    	
    	System.out.println(ansx +" " + ansy);
    }
}

 

결과