사용자 도구

사이트 도구


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()

토론

댓글을 입력하세요:
B N E A E
 
ps/problems/boj/1069.txt · 마지막으로 수정됨: 2022/02/17 16:43 저자 teferi