[백준/1069] 집으로 (Python)

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

1069번: 집으로

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:43:00

 

---

 

문제 설명

 

 

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

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

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

6 8 5 3

 

출력 예시

 

6.0

 

 

---

 

풀이

 

여러 가지 조건을 생각해 볼 수 있겠다.

 

• T / D가 1보다 작거나 같은 경우 : 이 경우는 1초에 1번 이동보다 점프가 비효율이거나, 다를 바 없는 케이스이다. (0, 0)까지 직접 움직이는 게 무조건 효율적이다. 따라서 정답은 (X, Y) ~ (0, 0)까지의 거리 dist가 된다.
• T / D가 1보다 큰 경우 : 이 경우를 살펴보도록 하자.
  • 1. 직선 주행 : 거리를 dist라고 둘 때, 우선은 (X, Y)에서 (0, 0)까지 일직선상으로 움직이는 경우가 있을 것이다. (dist//D)만큼을 우선 점프한다고 하자. 그렇다면 초기 비용으로 (dist // D * T)가 소요되며, 남은 거리는 0과 T사이의 값이 된다. 이 거리를 d라고 두자.
    
    

    

    
    첫 번째로, 한 번 T를 더 간 후 지나친 거리만큼 돌아오는 경우가 있겠다. 이 경우는 한 번 점프를 수행하고, 지나친 거리만큼 걸어오므로 추가 소요시간으로 T + (D - d)가 소요된다. 두 번째로, 이 지점에서 바로 걸어오는 경우가 있다. 이 경우 추가 소요시간으로 d가 소요된다.
    
    
  • 2. 삼각형 주행 : 아예 점프만 수행하여 도착하는 방법도 있다.
    

    

    n*D만큼 약간 사선으로 움직이고, 마지막에 방향을 틀어 D만큼 움직이면 삼각형을 그리며 도착할 수 있다. 삼각형의 성립 조건상 두 변의 길이의 합은 다른 한 변의 길이보다 무조건 커야 하며, 그 값 n은 최소여야 하므로 n = max(1, dist // D)가 성립한다.

 

1, 2번 주행 모두를 고려하여 최솟값을 도출하면 해결할 수 있다.

 

 

풀이 코드

from collections import deque

X, Y, D, T = map(int, input().split())
dist = (X**2 + Y**2) ** 0.5

if D/T <= 1 :
  print(dist)
  exit()

direct = dist // D * T
answer = direct + min(dist % D, T + (D - dist % D))
answer = min(answer, max(2*T, direct + T))
print(answer)

풀이 완료!