[Python] 1069번 집으로

1069번: 집으로 (acmicpc.net)

1069번: 집으로

---

 

22/09/01

 

 

이 문제는 참 창의적인 문제이다. 문제 풀면서 참 감탄한 문제이다.

 

발상이 굉장히 독특하긴 한데, 수많은 예제들을 보고 이를 쉽게 유추해낼 수 있어서 참 다행이었다.

 

만약 이 문제가 이렇게까지 예제 입력이 많이 주어지지 않았더라면 지금보다 난이도가 더 높게 매겨지지 않았을까 싶다.

---

 

문제 접근 방식:

 

처음에 살짝 그리디적인 방법으로 접근했다.

 

이후 이 방법을 뼈대로 하여 고쳐가며 문제를 해결하였다. 물론, 전체적인 방법론 자체는 그리디적인 사고에 기반을 둔 풀이이다.

 

이동 방식이 점프와 걸어가는 것, 두가지 방법이 있는데 만약 점프하는 것이 걸어가는 것보다 더 느리다면, 굳이 걸어갈 필요가 없다고 생각했다.

 

그래서 여기서 두가지 케이스로 나뉜다고 생각했다.

 

1. 점프가 더 느린 경우

2. 점프가 더 빠른 경우

 

첫 번째 경우는 당연히 점프가 더 느리기 때문에 그냥 걸어가는 게 이득이다.

 

따라서 그냥 목적지까지 걸어가면 된다.(그 시간을 재면 된다.)

 

만약 점프가 더 빠른 경우라면, 최대한 점프를 많이 해서 가는 것이 더 이득이라고 생각했다.(왜냐하면 점프가 더 빠르니깐)

 

근데, 여기서 조금 케이스가 갈릴 것이라고 생각했다.

 

왜냐하면 일반적인 그리디와는 다르게, 점프하는 것은 목적지를 지나칠 수도 있어서 되돌아가는 시간이 더 걸릴 수도 있다고 생각했기 때문이다.

 

그래서 목적지를 중심으로 하고 점프 거리를 반지름으로 한 원을 하나 생각했다.

 

점프를 하다가 그 원 안에 들어가게 된다면 더이상 점프를 하는 행위는 이득을 보는 것이 아니라고 판단했다.

 

그래서 그 원 직전까지 점프했다가 걸어가는 방법 하나와 그 원 안에 들어가서 목적지를 넘어가서 다시 되돌아가는 방법 하나, 둘 중 하나의 min함수를 취해주면 된다는 생각을 했다.

 

그렇게 문제를 접근했더니, 예제 일부만 맞고 전부가 맞지는 않았다.

 

알고 보니, 나는 항상 출발지에서 목적지로 이동할 때, 직선으로 움직인다는 것을 전제하고 문제를 접근했던 것이다.

 

실제 문제는 이차원이기 때문에, 직선으로 움직이지 않는 방법, 다시 말해 각도를 살짝살짝 꺾으며 점프를 하는 경우가 더 최단 시간이 걸릴 수도 있다.

 

이를 고려했더니 맞았습니다를 받았다.

 

정리하자면, 다음 그림과 같다.

 

최솟값이 나올 수 있는 3가지 경우

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1069번 집으로
# 기하학, 애드혹
from math import *
x, y, d, t = map(int, input().split())
distance = sqrt(x*x + y*y)
if d > t:  # 점프 속도가 걷는 것보다 더 빠르면
    total_time = 0
    i = max(ceil(distance / d), 2) # 점프만 할 때의 경우에서의 점프 횟수
    while distance >= d: # 일직선 상에서 직전까지 점프를 한다
        distance -= d
        total_time += t
    k = min(t+d-distance, distance)  # 일직선 상에서의 두 가지 경우 중 최소값
    total_time += k
    print(min(total_time, i*t)) # 일직선 상에서 움직이는 경우와 점프만 할 때의 경우 중 최솟값
else:
    print(distance)