백준 / 1069 집으로 python3

www.acmicpc.net/problem/1069

1069번: 집으로

현재 위치 (x,y)에서 (0,0)으로 어떻게 최소 시간에 올지 구하는 문제입니다. 

가는 방법은 그냥 걸어가는 것과 점프가 있습니다. 그냥 걷는 것은 1초에 1만큼, 점프는 T초에 D만큼 움직입니다.

 

처음에는 움직이는 경우를 x,y 축으로만 생각했었는데 테스트 케이스를 보니 대각선도 움직일 수 있습니다. 가능한 경우가 많을 거라 예상했지만 의외로 몇 가지 없었습니다.

 

현재 위치에서 0,0 까지 거리를 dist라 하겠습니다.

 

- dist >= D 일 때

1. 그냥 걷기

2. 점프를 최대한 많이 dist 방향으로 진행 후 걷기

3. 2번 경우에서 1번 더 점프하기 => 이등변 삼각형 같은 것을 생각하면 어떤 특정 지점까지 점프를 계속해서 무조건 도달할 수 있는 포인트가 나옵니다. 그러므로 점프만으로 0,0에 반드시 도착할 수 있으므로 2번 경우의 점프 횟수 +1이 점프만으로 도착하는 최소 경로입니다.

 

- dist < D 일 때

1. 그냥 걷기

2. 점프 한 번하고 걸어서 돌아가기

3. 점프 2번 => 이것도 위와 마찬가지로 점프 2번으로 0,0에 도착할 수 있습니다.

 

위 경우들 중 최솟값을 구하면 됩니다. (오차: 1e-9)

 

코드는 다음과 같습니다.

import sys
X, Y, D, T = map(int,sys.stdin.readline().split())

dist = (X**2 + Y**2)**0.5

"""
dist가 D보다 클 때(같을 때 포함):
1. 그냥 걷기
2. 점프를 dist 방향으로 최대한 많이 + 걷기
3. 점프만으로 dist에 도달할 수 있는 포인트 무조건 존재
(이등변 삼각형 생각하면 쉬움) => 최소는 dist 방향으로 최대 점프 횟수 + 1

dist가 D보다 작을 때:
1. 그냥 걷기
2. 점프 1번하고 걸어오기
3. 점프 2번 하기 (이등변 삼각형)

위 경우 중 최소값 구하면 됨.
"""

# jump = dist 방향으로 점프할 수 있는 최대 경우
jump = dist//D

if dist >= D:
    case1 = T * jump + (dist - (D * jump))
    case2 = dist
    case3 = T * (jump + 1)
    
    result = min(case1, min(case2, case3))
    result = round(result,9)
    print(result)

else:
    case1 = T + (D - dist)
    case2 = dist
    case3 = T * 2
    
    result = min(case1, min(case2, case3))
    result = round(result,9)
    print(result)