Sign in Subscribe
PS

[PS] BOJ 1393 / 음하철도 구구팔

Minjun Kim

• 4 min read
[PS] BOJ 1393 / 음하철도 구구팔
Thumbnail: Photo by Chris Yang (Unsplash)
문제 링크: https://www.acmicpc.net/problem/1393

옛날 학생 시절에 배운 "수선의 발" 개념을 사용하면 어렵지 않게 계산할 수 있습니다.

풀이

수선의 발?

어느 한 직선과 직선 위에 있지 않은 점 P가 있을 때, 점 P에서 직선 위에 수직이 되도록 내린 점을 수선의 발이라고 합니다.

여러 방법으로 구할 수 있지만, 문제에서 직선 위의 한 점 $(x_e, y_e)$와 기울기($dy/dx$), 그리고 점 P $(x_s, y_s)$가 주어지므로 직선과 수직이 되며, 점 P를 지나는 직선을 찾아 두 직선의 교점을 구하는 방법으로 계산할 수 있습니다.

두 직선의 교점은 두 직선을 연립 방정식으로 만든 뒤, 식을 정리해 계산했습니다.

# 1. 기준 직선 (철도)
# 기울기 (dy/dx)이고 (x_e, y_e)를 지나는 직선
# dy/dx = (y - y_e) / (x - x_e)
# dy(x - x_e) = dx(y - y_e)
# dy * x - dx * y = dy * x_e - dx* y_e

# 2. 수직이 되는 직선 (정거장)
# 기울기 (-dx/dy)이고 (x_s, y_s)를 지나는 직선
# -dx/dy = (y - y_s) / (x - x_s)
# -dx * x + dx * x_s = dy * y - dy * y_s
# -dx * x - dy * y = -dx * x_s - dy * y_s
# dx * x + dy * y = dx * x_s + dy * y_s

# 3. 연립방정식의 해 구하기 (두 직선의 교점)
# dy * x - dx * y = dy * x_e - dx * y_e (1)
# dx * x + dy * y = dx * x_s + dy * y_s (2)

# (1)에 dx, 2에 dy를 곱한 후 서로 빼 x를 제한다.
# (dx * dy) * x - dx^2 * y = (dx * dy) * x_e - dx^2 * y_e (1)
# (dx * dy) * x + dy^2 * y = (dx * dy) * x_s + dy^2 * y_s (2)

# (2)에서 (1)을 뺀 뒤 식을 y에 대해 정리한다.
# (dy^2 + dx^2) * y = (dx * dy) (x_s - x_e) + dy^2 * y_s + dx^2 * y_e
y = ((dx * dy) * (x_s - x_e) + dy * dy * y_s + dx * dx * y_e) // (dy * dy + dx * dx) # 항상 정수 답이 나오는 입력만 주어짐

# (1)을 이용해 y에 대한 x를 찾는다.
# dy * x = dx * (y - y_e) + dy * x_e
x = dx * (y - y_e) // dy + x_e
print(x, y)

수선의 발 공식으로 좌표 찾기

예외 처리하기

단, 문제에서 주어지는 철도는 온전한 직선이 아니라, 현재 위치 $(x_e, y_e)$에서부터 1초당 $d_{x}, d_{y}$만큼 증가하는 방향으로만 존재합니다. 또, $d_{x}$ 또는 $d_{y}$가 0인 경우도 고려해야 합니다.

  • dx, dy가 정류장과 멀어지는 방향이라면, 현재 위치가 가장 가까운 지점입니다.
  • dx 또는 dy가 0이라면, 해당 축의 좌표는 현재 위치와 같습니다.
# 정류장과 반대 방향으로 이동할 때 예외처리
neg_x = False
neg_y = False
if (dy < 0 and y_s - y_e > 0) or (dy > 0 and y_s - y_e < 0) or (dx < 0 and x_s - x_e > 0) or (dx > 0 and x_s - x_e < 0):
    print(x_e, y_e)

# dx나 dy가 0일 때 예외처리
elif dx == 0:
    if dy == 0:
        print(x_e, y_e)
    else:
        print(x_e, y_s)
elif dy == 0:
    print(x_s, y_e)
else:
    # 수선의 발 공식으로 구하기
    ...

예외 처리하기

전체 코드

input = open(0).readline
x_s, y_s = tuple(map(int, input().split()))     # 정류장 위치
x_e, y_e, dx, dy = map(int, input().split())    # 현재 위치 x_e, y_e, 초당 x/y축 변화량 dx, dy

# 정류장과 반대 방향으로 이동할 때 예외처리
neg_x = False
neg_y = False
if (dy < 0 and y_s - y_e > 0) or (dy > 0 and y_s - y_e < 0) or (dx < 0 and x_s - x_e > 0) or (dx > 0 and x_s - x_e < 0):
    print(x_e, y_e)

# dx나 dy가 0일 때 예외처리
elif dx == 0:
    if dy == 0:
        print(x_e, y_e)
    else:
        print(x_e, y_s)
elif dy == 0:
    print(x_s, y_e)
else:
    # 1. 기준 직선 (철도)
    # 기울기 (dy/dx)이고 (x_e, y_e)를 지나는 직선
    # dy/dx = (y - y_e) / (x - x_e)
    # dy(x - x_e) = dx(y - y_e)
    # dy * x - dx * y = dy * x_e - dx* y_e

    # 2. 수직이 되는 직선 (정거장)
    # 기울기 (-dx/dy)이고 (x_s, y_s)를 지나는 직선
    # -dx/dy = (y - y_s) / (x - x_s)
    # -dx * x + dx * x_s = dy * y - dy * y_s
    # -dx * x - dy * y = -dx * x_s - dy * y_s
    # dx * x + dy * y = dx * x_s + dy * y_s

    # 3. 연립방정식의 해 구하기 (두 직선의 교점)
    # dy * x - dx * y = dy * x_e - dx * y_e (1)
    # dx * x + dy * y = dx * x_s + dy * y_s (2)

    # (1)에 dx, 2에 dy를 곱한 후 서로 빼 x를 제한다.
    # (dx * dy) * x - dx^2 * y = (dx * dy) * x_e - dx^2 * y_e (1)
    # (dx * dy) * x + dy^2 * y = (dx * dy) * x_s + dy^2 * y_s (2)

    # (2)에서 (1)을 뺀 뒤 식을 y에 대해 정리한다.
    # (dy^2 + dx^2) * y = (dx * dy) (x_s - x_e) + dy^2 * y_s + dx^2 * y_e
    y = ((dx * dy) * (x_s - x_e) + dy * dy * y_s + dx * dx * y_e) // (dy * dy + dx * dx) # 항상 정수 답이 나오는 입력만 주어짐

    # (1)을 이용해 y에 대한 x를 찾는다.
    # dy * x = dx * (y - y_e) + dy * x_e
    x = dx * (y - y_e) // dy + x_e
    print(x, y)

solution.py