백준 1393번: 음하철도 구구팔

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

 

수의 범위가 -100 ~ 100인 도착점과 시작점에 대한 2차원 좌표와 이동 방향이 주어질 때, 시작점에서 이동 방향으로 증가하는 좌표들 중 좌표가 모두 정수이면서 도착점과의 거리가 가장 짧을 때의 좌표를 출력하는 문제이다.

 

모든 좌표는 정수로 주어지나 x축 이동량, y축 이동량이 1이 아닌 공약수가 존재하면 중간의 정수 좌표를 지나치게 되므로 이동량의 최대공약수로 각각의 이동량을 나누어준다.

int gcd = gcd(dx, dy);
dx /= gcd;
dy /= gcd;

private static int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

 

 

이후, 공약수 * 200 만큼 좌표를 이동해주면서 거리가 최소가 될 때 최적좌표를 업데이트한다.

double minDistance = Math.sqrt(Math.pow(startX - targetX, 2) + Math.pow(startY - targetY, 2));
int currentMinX = startX, currentMinY = startY;
for (int i = 1; i <= 200 * gcd; i++) {
    int nx = startX + dx * i, ny = startY + dy * i;
    double distance = Math.sqrt(Math.pow(nx - targetX, 2) + Math.pow(ny - targetY, 2));
    if (minDistance > distance) {
        minDistance = distance;
        currentMinX = nx;
        currentMinY = ny;
    }
}

 

 

결과 코드는 다음과 같다.

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

public class 음하철도구구팔1393 {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int targetX = Integer.parseInt(st.nextToken()), targetY = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int startX = Integer.parseInt(st.nextToken()), startY = Integer.parseInt(st.nextToken());
        int dx = Integer.parseInt(st.nextToken()), dy = Integer.parseInt(st.nextToken());
        int gcd = gcd(dx, dy);
        dx /= gcd;
        dy /= gcd;
        double minDistance = Math.sqrt(Math.pow(startX - targetX, 2) + Math.pow(startY - targetY, 2));
        int currentMinX = startX, currentMinY = startY;
        for (int i = 1; i <= 200 * gcd; i++) {
            int nx = startX + dx * i, ny = startY + dy * i;
            double distance = Math.sqrt(Math.pow(nx - targetX, 2) + Math.pow(ny - targetY, 2));
            if (minDistance > distance) {
                minDistance = distance;
                currentMinX = nx;
                currentMinY = ny;
            }
        }
        System.out.print(currentMinX + " " + currentMinY);
    }
    
    private static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}