[Silver I] 음하철도 구구팔 - 1393
성능 요약
메모리: 2020 KB, 시간: 0 ms
분류
브루트포스 알고리즘, 수학, 정수론
제출 일자
2025년 1월 11일 14:53:00
문제 설명
최백준은 음하철도 구구팔에 탔다.
문제는 구구팔의 기장인 조교 김재홍이 반쯤 미쳐서 열차를 멈추지 않는다는 것이다. 그래서 최백준은 달리고 있는 열차에서 뛰어내려야 한다.
그런데 뛰어내릴 때 정류장 까지 거리가 너무 멀면 마이 아플 수 있다.
그래서 철도가 정류장에 가장 많이 근접했을 때 뛰어내리고자 한다.
어디서 뛰어내려야 하는가?
입력
첫번째 줄에는 xs와 ys가 주어진다. 이는 정류장의 위치가 (xs, ys)임을 의미한다.
두번째 줄에는 xe, ye, dx, dy가 주어진다. 이는 현재 열차 위치가 (xe, ye)이고, 열차가 1초마다 x가 증가하는 방향으로 dx만큼, y가 증가하는 방향으로 dy만큼 이동함을 의미한다
주어지는 모든 수는 -100이상, 100이하의 정수이다.
출력
최백준이 뛰어내릴 위치의 x좌표와 y좌표를 출력한다. 뛰어내릴 위치의 좌표가 항상 정수인 입력만 주어진다.
문제 풀이
- 기차의 이동 벡터 최적화
- 기차의 이동 방향 (dx, dy)를 최소 단위로 줄인다
- 예: (4,6)으로 이동한다면 GCD인 2로 나눠서 (2,3)으로 변환. 이렇게 하면 모든 가능한 정수 좌표를 놓치지 않고 확인할 수 있다
- 거리 계산과 탐색
- 각 시점 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;
}
Studying Everyday