백준 / 1393 / 음하철도 구구팔 / 파이썬, python, pypy

1393번: 음하철도 구구팔

 

처음에 문제를 보고 한 점(xs, ys)에서 선분(xe, ye와 xe+dx, ye+dy를 지나는)까지의 최단거리를 구하려했다.

 

그러나 골드 5 난이도보단 높은 듯 하여, 브루트포스 방법을 생각하였다.

 

distance(curx, cury) < distance(curx+dx, cury+dy)일때 계속 curx, cury에 dx, dy를 더해주면서 반복하면서 구하려 하였는데,

 

문제의 예제를 보면 3, 3이 나온다.

 

결국 1초 단위로 움직이는게 아니라 연속적인 이동 중에 체크를 해야하는데, dx, dy는 항상 정수라는 힌트가 주어졌다.

 

즉 dx, dy의 최대공약수(GCD)를 구한 뒤 dx //= gcd(dx, dy), dy //= gcd(dx, dy)를 한 뒤,

 

반복문에 조건을 같게 설정하면 쉽게 답을 구할 수 있었다.

 

 

처음에 골드 5 치고 브루트포스로 하면 쉽게 풀수있다고 생각해서 골드문제가 맞나? 라는 생각을 하였는데, 한가지 트릭을 넣어서 난이도를 높힌듯하다... (그러나 그래도 실버1,2 정도 수준이지 않나.. 라고 생각된다.)

 

 

아래의 코드 중 get_gcd()의 경우 math.gcd()를 사용해도 되지만, 원리를 아는게 중요하여 한번 더 복습을 위해 추가하였다.

또한, math.sqrt를 **0.5로 사용해도 같으므로, import math도 제거하면 더 깔끔한 코드를 얻을 수 있다.

import sys
import math
 
def get_gcd(a, b):
    while b:
        a, b = b, a%b
    return a
 
def check_distance(x, y):
    return math.sqrt((x - xs)**2 + (y - ys)**2)
 
xs, ys = map(int, sys.stdin.readline().split())
xe, ye, dx, dy = map(int, sys.stdin.readline().split())
 
d_gcd = get_gcd(dx, dy)
dx, dy = dx//d_gcd, dy//d_gcd
 
curx, cury = xe, ye
while check_distance(curx, cury) > check_distance(curx + dx, cury + dy):
    curx += dx
    cury += dy
 
print(curx, cury)