백준 1069 집으로

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

(x, y)위치에서 (0, 0)으로 가능한 빨리 가는 방법을 찾는 문제이다. 이 때 1초에 1만큼 움직이거나 T초에 D만큼 점프하는 방법을 선택할 수 있다. 좌표상에서 기하학적인 사고방식을 요구하는 문제라서 한번 정리를 해봤다. 먼저 D/T > 1이 아닌경우 무조건 걷는것이 빠르다는 것을 유의하자.

이제 점프가 걷는것보다 빠르다는 경우를 가정하고 문제를 접근하겠다. (x, y)위치에서 영점으로 향하는 가장 빠른 길은 영점과 (x, y)를 이은 직선을 따라 점프하는 것이다. 따라서 점프하는 방법을 통해 원점에서 2D 이하인 지점에 도달할때까지 반복해서 점프하자. 남은 거리에 따라서 2가지 방법이 존재한다.

1. 원점까지 거리가 D이상 남았을 경우
   2가지의 방법이 존재한다. 녹색 선분을 따라 1번 점프하고 남은 거리를 걸어가는 경우와 빨간색 선분을 따라 2번 점프해 가는 방법이 존재한다. 따라서 두 방법 중 시간이 덜 걸리는 방법을 택해주면 된다.
2. 원점까지 거리가 D보다 작을 경우
   3가지의 방법이 존재한다. 검은색 선분을 따라 걸어가는 경우와 녹색 선분을 따라 1번 점프하고 원점을 지나친 거리만큼 걸어서 돌아가는 방법, 마지막으로 빨간 선분을 따라 2번 점프하는 방법이다. 마찬가지로 세 방법 중 시간이 덜 걸리는 방법을 택해주면 된다.

쉽게 착각하는 오류로 원점과 (x, y)를 이은 직선상에서만 이동을 할 수 있다고 착각하는 것이다. 하지만 여기는 기하가 적용되는 2차원이기 때문에 삼각형을 이루듯이 이동하는 방법이 존재한다는 것을 명심하자.

• 전체 코드

import Foundation
let line = readLine()!.split(separator: " ").map{Double(String($0))!}
let x = line[0], y = line[1], D = line[2], T = line[3]
let d = sqrt(x*x + y*y)
if D <= T {
    print(d)
}
else {
    var spentTime:Double = 0
    var lastLeng = d
    while lastLeng >= 2*D {
        lastLeng -= D
        spentTime += T
    }
    if lastLeng <= D {
        spentTime += min(2*T, lastLeng, D-lastLeng+T)
    }
    else {
        spentTime += min(2*T, T+lastLeng-D)
    }
    print(spentTime)
}