[🥇3 / 백준 1069 / 파이썬] 집으로

 

1069번: 집으로

 

문제

은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다.

첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법은 점프하는 것이다. 점프를 하게 되면, T초에 D만큼 움직인다. 점프는 일직선으로만 할 수 있고, 정확하게 D칸만 움직일 수 있다.

위의 두 가지 방법을 이용해서 집에 돌아오는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오. 꼭 한 가지 방법만 사용해야 되는것이 아니고, 두 가지 방법을 적절히 조합해서 가장 빠른 시간을 구하는 것이다.

입력

첫째 줄에 네 정수 X, Y, D, T가 주어진다.

출력

첫째 줄에 집에 돌아오는데 걸리는 시간의 최솟값을 출력한다. 절대/상대 오차는 10^-9까지 허용한다.

제한

• 1 ≤ X, Y ≤ 1,000
• 1 ≤ D, T ≤ 10,000

 

예제 입력 1 6 8 5 3	예제 출력 1 6.0
예제 입력 2 3 4 6 3	예제 출력 2 4.0
예제 입력 3 318 445 1200 800	예제 출력 3 546.9451526432975
예제 입력 4 400 300 150 10	예제 출력 4 40.0
예제 입력 5 6 8 3 2	예제 출력 5 7.0
예제 입력 6 10 10 1000 5	예제 출력 6 10.0

 

풀이

 

점프를 적절히 이용하여 0,0 까지 이동해야 한다.

예제에 거의 대부분의 예외 케이스가 들어있는 것 같다.

 

다음과 같이 총 4가지로 분류할 수 있다.

 

• 점프를 이용하지 않는 경우
• 점프를 이용하여 (0,0)을 지나치는 경우
• 점프를 이용하여 (0,0) 직전에 멈추는 경우
• 점프를 두 번 이상 했을 때의 코스트가 총 거리보다 짧을 때

 

네 번째 경우가 키 포인트라고 생각한다.

 

예제 6번을 살펴보자.

실제와는 다르게 생겼지만 파란색 선분이 직선 거리라고 했을 때 소요 시간은 약 14.142가 나온다.

허나, 점프를 두 번 이용하여 다른 지점을 찍고 온다면 거리는 엄청나게 길지만 소요 시간은 10초가 된다.

 

 

단, 두 번이 아니라 그 이상도 마찬가지로 거리는 길지만 코스트가 작을 수 있으므로 유의하여 코드를 작성해야 한다.

 

import sys, math
input = sys.stdin.readline

x,y,d,t = map(int,input().split())
d1 = (x**2+y**2)**0.5

# 점프 이용
n=max(d1//d,1)
d2 = min(abs(d1-d*n)+t*n, d1-d*n+d+t*n) # (0,0) 지나칠 때, 안 지나칠 때

# 점프 n번(n>=2)이 빗변보다 길때
d3 = max(math.ceil(d1/d),2)*t

print(min(d1,d2,d3))