백준 1069번 집으로

X,Y에서 0,0으로 갈 수 있는 가장 빠른 시간을 구하는 문제입니다. 이동하는 방법은 두 가지로 걷거나 점프 할 수 있습니다. 걷기는 1초에 1만큼씩 움직이는 것입니다. 점프는 T초에 D만큼 움직일 수 있고 일직선으로만 할 수 있고 정확하게 D칸만 움직일 수 있습니다.

 

시도 1.

초반에는 입력에 대한 출력을 이해하는 것도 잘 되지 않았습니다.

 

예제 입력 1

# 입력
6 8 5 3

# 출력
6.0

6,8에서 0,0까지의 거리가 10이므로 두 번의 점프로 이동하면 0,0에 도착 할 수 있습니다.

예제 입력 1, 2, 3은 어느정도 생각하면 바로 떠올랐지만 예제 입력 4나 6은 바로 생각이 떠오르지 않아 힘들었습니다...

 

예제 입력 4

# 입력
400 300 150 10

# 출력
7.0

400,300에서 0,0까지의 거리는 500이고 이를 세 번 점프하면 40,30 칸에 도착하고 시간은 30을 썼다고 생각했습니다. 남은 거리는 50이지만 10의 시간만 더 쓰고 집에 도착 할 수 있는 방법이 떠오르지 않았습니다.

 

그래서 X,Y에서 0,0으로 이동하는 방법이 위처럼 그저 X,Y-> 0,0 방향으로 일직선으로만 움직이는 것은 아닐 것이라고 생각했습니다.

 

시도 2.

문제를 계속해서 다시 읽으면서 생각을 해보았습니다.

점프의 경우 일직선으로만 이동 가능하고 무조건 D만큼 이동 가능했습니다. 그래서 현재 지점에서 D만큼 이동 할 수 있는 칸에 대해 생각해봤습니다.

예시 그림1

한 정점에서 같은 거리에 있는 점들에 대해 생각하니 원이 그려지게 되었습니다. 이 그림을 그리고 나니 움직일 수 있는 다른 방법을 떠올릴 수 있었습니다.

예시 그림2

위의 그림은 8,6에서 이동을 시작하고 D=6일 경우입니다.

8,6에서 0,0으로 이동하는 방법은 다음과 같습니다.

1. 한 번 점프를 한 뒤 남은 거리를 걸어간다
2. 두 번 점프를 한 뒤 넘어간 곳에서 남은 거리를 걸어간다
3. 빨간색 화살표가 가리키는 지점까지 점프를 해서 이동 한 뒤 0,0으로 점프를 한다.

3번이 새롭게 추가된 방식인데, 1,2와 비교하여 더 빠르게 이동 할 수 있는 것이 정답이 될 것이라고 생각했습니다.

 

그래서 여러가지 경우의 수를 더 세분화해서 나누어 봤습니다.

 

점프 + 걷기

• 0,0까지의 거리에서 점프를 할 수 있는 만큼하고 나머지 거리를 걸어간다
• 0,0까지의 거리에서 점프를 할 수 있는 만큼 한 번 더 점프한 다음, 다시 0,0까지 걸어간다

점프만으로 이동

• 0,0까지 점프만으로 이동이 가능 할 경우 점프만으로 이동
• 거리//D >= 1 인 경우 위의 그림처럼 두 번의 점프로 이동
• 거리//D < 1인 경우 거리//D -1 만큼 점프하고 위의 그림처럼 두 번의 점프로 이동

 

위와 같이 세분화 한 뒤 이를 이용해 최소값을 구해줄 수 있도록 했습니다.

d=(X**2+Y**2)**(1/2)
share=d//D
remain=d%D
minValue = min(share * T + remain,(share+1)*T + D-remain)

if d%D==0:
    minValue=min(minValue,share*T)
else:
    if share<=1:
        minValue=min(minValue,2*T)
    else:
        minValue=min(minValue,(share+1)*T)

 

하지만, 틀렸습니다 가 나왔습니다...

그래서 다른 방법이 있는지 확인해보고 세분화한 것 중에 포함되지 않은 것들을 찾아보았습니다.

그랬더니! 일직선으로 이동 할 때 걷기로만 이동하는 경우가 포함되지 않은 것을 확인했고 이를 대입하여 통과했습니다.

d=(X**2+Y**2)**(1/2)
share=d//D
remain=d%D
minValue = min(d,share * T + remain,(share+1)*T + D-remain) # 추가

if d%D==0:
    minValue=min(minValue,share*T)
else:
    if share<=1:
        minValue=min(minValue,2*T)
    else:
        minValue=min(minValue,(share+1)*T)

print(minValue)

 

 

 

해결

이번 문제는 예제 입력도 이해하는 것에 어려움을 겪었던 문제입니다. 그래도 다른 이동 방식을 빠르게 찾아내서 다행이었던 것 같습니다.