ps:problems:boj:1069
집으로
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 1069 |
문제명 | 집으로 |
레벨 | 골드 2 |
분류 |
애드혹 |
시간복잡도 | O(1) |
사용한 언어 | Python |
제출기록 | 32976KB / 68ms |
최고기록 | 56ms |
해결날짜 | 2022/02/17 |
풀이
- 문제가 좀 헷갈리게 적혀있다. 걷는거는 그냥 초속 1로 이동한다는 뜻이고, 점프는 한번 뛰면 무조건 T초를 채워서 D만큼의 거리를 이동한다는 뜻이다.
- 먼저 엣지 케이스를 정리하자. 점프했을때 T>=D 라면 그냥 걷는것보다 느리다. 점프를 할 이유가 없다.
- 이번에는 집까지의 거리가 D보다 작은 경우이다. 1)점프를 2번 해서 바로 집으로 가는 방법과(시작위치, 첫 점프 도착 위치, 집 이 삼각형을 이룬다), 2)집 방향으로 점프해서 집을 지나쳤다가 걸어서 다시 돌아오는 방법과, 3)그냥 점프 안하고 걸어서만 가는 방법중에서 가장 빠른쪽을 고르면 된다.
- 집까지의 거리가 D보다 긴 경우를 생각하자. 집까지의 거리가 D*a+b 라고 하자. 이번에는 점프를 a+1번 해서 집에 도착하는 방법과, 점프를 a번 하고 b만큼을 걸어가는 방법중에서 고르면 된다. 아까와 달리 집을 지나쳐서 점프했다가 돌아오는 것은 고려할 필요가 없다. 점프해서 집을 지나치려면 a+1번의 점프가 필요한데, 이것은 방향을 바꿔서 점프했다면 바로 집에 도착할수 있기 때문이다.
- 이렇게 세개의 케이스로 나눠서 답을 계산하면 된다. 시간복잡도는 O(1)
코드
"""Solution code for "BOJ 1069. 집으로".
- Problem link: https://www.acmicpc.net/problem/1069
- Solution link: http://www.teferi.net/ps/problems/boj/1069
"""
import math
def main():
X, Y, D, T = [int(x) for x in input().split()]
dist = math.sqrt(X * X + Y * Y)
if D <= T:
answer = dist
elif D > dist:
answer = min(T + T, T + D - dist, dist)
else:
jump_count = int(dist / D)
answer = jump_count * T + min(T, dist - D * jump_count)
print(answer)
if __name__ == '__main__':
main()
ps/problems/boj/1069.txt · 마지막으로 수정됨: 2022/02/17 16:43 저자 teferi
토론