[백준 / BOJ] 1393 음하철도 구구팔 (Java)

문제

출처 : https://www.acmicpc.net/problem/1393

1393번: 음하철도 구구팔

최백준은 자신이 탄 음하철도 구구팔이 정류장과 가장 근접했을때 뛰어내릴려고한다.

자신이 탄 철도의 위치와, 이동방향, 정류장의 위치가 주어질때, 최백준이 뛰어내리는 위치를 구하는 문제다.

 

풀이

"뛰어내릴 위치의 좌표가 항상 정수인 입력만 주어진다." 조건때문에, 완전탐색으로 풀수있는 문제였다.

이게없었으면 이동하는 소수점단위까지 계산해야하므로, 결정문제로 변형후 삼분탐색으로 풀어야한다

 

이런 문제가 실제로 있다 아래 링크 참조

https://www.acmicpc.net/problem/1087

1087번: 쥐 잡기

다시 원래 문제로 돌아가서,

이 문제 또한, 움직이는 중간에 최소위치가 될수있다. 즉, 매 초마다 (2,4) 만큼 움직이는 기차는 0.5초에 (1,2)만큼 움직여있을것이고, 이때 정류장과의 거리가 최소가 될수있는것이다. (문제의 예제 1이 그렇다)

하지만 "뛰어내릴 위치의 좌표가 항상 정수인 입력만 주어진다."가 있기때문에 소수점까지 고려해줄필요는없다.

 

따라서, 기차가 이동할수있는 최소 정수거리를 구해서 이동시키면된다.

 

또한, 2차원평면상에서 한 방향으로만 이동하는 점A(이 문제에서는 기차가 될것이다)는 점B(정류장)과 멀어지기 시작하면 더 이상 가까워질 방법은없다. 

따라서, 처음으로 멀어지기 시작하는위치의 전 위치가 정류장과의 거리가 최소가 되는 지점인걸 알수있다.

 

로직은 다음과 같다.

 

1. 기차가 이동할수있는 최소 정수거리를 구한다.

- dy, dx의 GCD를 구한후 각각에 나눠준다.

 

2. 탐색시키며, 처음으로 멀어지기 시작하는 위치를 찾는다. 찾았다면, 현재위치(y,x)에서 기차의 최소 이동거리를 뺀다. (-dy,dx)

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1393%20%EC%9D%8C%ED%95%98%EC%B2%A0%EB%8F%84%20%EA%B5%AC%EA%B5%AC%ED%8C%94/Main.java

devxb/JJUNalgo