BOJ_1393_음하철도 구구팔 (Java, C++)

[Silver I] 음하철도 구구팔 - 1393

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

브루트포스 알고리즘, 수학, 정수론

제출 일자

2025년 1월 11일 14:53:00

문제 설명

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

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

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

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

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

입력

첫번째 줄에는 x_s와 y_s가 주어진다. 이는 정류장의 위치가 (x_s, y_s)임을 의미한다.

두번째 줄에는 x_e, y_e, dx, dy가 주어진다. 이는 현재 열차 위치가 (x_e, y_e)이고, 열차가 1초마다 x가 증가하는 방향으로 dx만큼, y가 증가하는 방향으로 dy만큼 이동함을 의미한다

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

출력

최백준이 뛰어내릴 위치의 x좌표와 y좌표를 출력한다. 뛰어내릴 위치의 좌표가 항상 정수인 입력만 주어진다.

문제 풀이

1. 기차의 이동 벡터 최적화

• 기차의 이동 방향 (dx, dy)를 최소 단위로 줄인다
• 예: (4,6)으로 이동한다면 GCD인 2로 나눠서 (2,3)으로 변환. 이렇게 하면 모든 가능한 정수 좌표를 놓치지 않고 확인할 수 있다

1. 거리 계산과 탐색

• 각 시점 t마다 기차의 위치: (xe + tdx, ye + tdy)
• 이 위치에서 정류장까지의 거리를 계산: (xs - 현재x)² + (ys - 현재y)² 거리가 가장 짧은 지점이 답이 된다.

주의할 점들

• 탐색 범위

  • 모든 입력값이 -100 ~ 100 사이이므로
  • 최대 거리는 200(x축) + 200(y축) = 400
  • 따라서 200번의 반복문이면 충분합니다

• 오버플로우 처리

  • 거리 계산시 제곱을 하므로 int 범위를 넘을 수 있음
  • 1LL *를 곱해서 long long으로 확실하게 처리

• GCD 처리

  • 이동 벡터를 최소화하면 불필요한 계산을 줄일 수 있음
  • (4,6) → (2,3)으로 바꾸는 것처럼 최적화

예: 기차가 (2,1)에서 시작해서 (2,4) 방향으로 움직일 때
정류장이 (5,2)에 있다면

움직임: (2,1) → (4,5) → (6,9) → ...
이 중에서 (3,3)이 정류장과 가장 가까운 지점이 됩니다.

코드

Java 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		st = new StringTokenizer(br.readLine());
		int x0 = Integer.parseInt(st.nextToken());
		int y0 = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int x1 = Integer.parseInt(st.nextToken());
		int y1 = Integer.parseInt(st.nextToken());
		int dx = Integer.parseInt(st.nextToken());
		int dy = Integer.parseInt(st.nextToken());
		
		int gcd = gcd(Math.abs(dx), Math.abs(dy));
	    if (gcd > 0) {
	        dx /= gcd;
	        dy /= gcd;
	    }
	    
	    long min = Long.MAX_VALUE;
	    int tx = x1, ty = y1;
	    
	    for (int t = 0; t < 200; t++) {
	        int currX = x1 + t * dx;
	        int currY = y1 + t * dy;
	        long dist = (long)(x0 - currX) * (x0 - currX) + (long)(y0 - currY) * (y0 - currY);
	        
	        if (dist < min) {
	            min = dist;
	            tx = currX;
	            ty = currY;
	        }
	    }
	    
	    bw.write(tx + " " + ty);
		bw.flush();
		bw.close();
		br.close();
	}

	private int gcd(int a, int b) {
		while (b != 0) {
	        int tmp = a % b;
	        a = b;
	        b = tmp;
	    }
	    return a;
	}
}

---

C++

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int x0, y0;
    cin >> x0 >> y0;

    int x1, y1, dx, dy;
    cin >> x1 >> y1 >> dx >> dy;

    int g = gcd(abs(dx), abs(dy));
    if (g > 0) {
        dx /= g;
        dy /= g;
    }

    long long min_dist = LLONG_MAX;
    int tx = x1, ty = y1;

    for (int t = 0; t < 200; t++) {
        int currX = x1 + t * dx;
        int currY = y1 + t * dy;
        long long dist = 1LL * (x0 - currX) * (x0 - currX) +
                         1LL * (y0 - currY) * (y0 - currY);

        if (dist < min_dist) {
            min_dist = dist;
            tx = currX;
            ty = currY;
        }
    }

    cout << tx << " " << ty << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}