백준 1069 (집으로)

백준 1069 (집으로)

문제 링크

문제 링크 : https://www.acmicpc.net/problem/1069

문제 접근

오랜만에 재미있는 문제를 들고왔습니다. 고등학교 3학년 때, 기하와 벡터 과목이 생각나는 문제입니다. 간단하게 요약하자면, 2차원 평면상에, 하나의 점이 (x,y)로 주어졌습니다.

1. 원점까지 1초당 1의 거리를 가는 방법 (거리 1당 1의 시간이 소모됩니다.) 
2. t초에 d만큼의 직선 거리를 사용해서 점프하는 방법

두 가지 방식을 선택해서, 원점까지 가는 최단 시간을 구하는 문제입니다. 처음 문제를 봤을 때, 축에 수직인 방향으로만 이동할 수 있다는 조건이 있는줄 알았습니다. 하지만 일직선 방향이라는 것이 수직인 거리가 아니므로, manhattan distance 문제가 아님을 알았습니다. 즉, 최소 단위만큼 움직일 때 방향은 전혀 관계가 없다는 의미입니다.

방향을 자유롭게 움직일 수 있음을 알았으므로, 적절히 잘 움직여 봅시다. 제일 간단한 방식은, 1초당 1의 거리를 가는 방법으로 원점까지 계속 뚜벅뚜벅 가는 방식입니다. 이 방식은 원점에서 (x,y)까지의 유클리드 거리라고 할 수 있겠습니다. 점프를 사용하지 않는 방법입니다.

그렇다면 이제 점프를 사용하는 방법을 알아보겠습니다.

1번의 점프를 사용하면, 갈 수 있는 점의 좌표들은

x^2 + y^2=n 위의 모든 점입니다. 

점프를 2회 이상 사용하는 방법을 생각해봅시다. 결론부터 말하자면

점프를 n회 (n>=2) 했을 때, 갈 수 있는 점의 좌표들은 
x^2 + y^2 <=nd 내부 모든 점 (x,y)의 집합의 원소입니다.

이유는 간단합니다. 방향이 자유롭기 때문에, 내가 어느 방향으로 가더라도, 다시 돌아올 수 있기 때문입니다. 자유로움은 위대하다

점프를 n회 반복했을 때, 내부에 점 P가 있는 하한의 n을 생각해봅시다. nt의 시간으로 P에 도착을 할 수 있습니다. 하지만 하나 더 고려해야 합니다. 내부에 점 P가 없는 상한의 n에 대해서, 남은 최단 거리를 1초당 1의 거리로 가는 방식도 고려를 해야 한다는 것입니다.

1초당 1의 거리로 가는 방식으로 남은 거리를 채우는 방법 vs 점프로 모든 것을 해결하는 방법 

을 비교해야 한다는 것입니다.

그렇다면, 총 4가지의 케이스가 생깁니다.

1. 단순히 그냥 가는 방법 
2. 점프를 한 번 하고 남은 거리를 그냥 가는 방법
3. 점을 포함하고, 최소한 점프를 하는 방법
4. 점을 포함하지 않고 최대한 가깝게 간 다음, 남은 거리를 그냥 가는 방법

아래 그림을 보면, 조금 이해하기 쉬울 수도 있습니다.

즉, 점프를 몇 번 할지의 싸움입니다. 점프를 2회 이상 했을 때, 점 P보다 원점에서 멀리 간다면 내부 모든 점을 갈 수 있다는 것이 문제를 푸는 핵심입니다.

소스 코드

import sys,math
x,y,d,t=map(int,sys.stdin.readline().split())
answer=math.sqrt((x**2)+(y**2))
base_distance=answer
count=float((int(base_distance//d)) + 1)
if count<=2 :
    count=2
#차례로 1번, 2번, 3번, 4번 방법입니다.
print(min(answer, t+ abs(base_distance - d) , float(count*t), (count-1)*t+abs(base_distance-(count-1)*d) ))

마무리하며

학창 시절이 생각나는 문제입니다. 요즘은 선택과목 시대라던데, 과외 학생은 미적분을 선택해서 과외할 때 재미가 없습니다. . . 기하가 더 재밌는데.. 아무튼 곧 개강이라는 사실이 믿기지 않습니다. 다음 문제에서 뵙겠습니다.