백준 1069번 집으로

문제

백은진은 지금 (x, y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 백은진은 다음과 같이 두 가지 방법으로 움직일 수 있다.

첫 번째 방법은 걷는것이다. 걸을 때는, 1초에 1만큼 움직인다.

두 번째 방법은 점프하는 것이다. 점프를 하게 되면, T초에 D만큼 움직인다. 점프는 일직선으로만 할 수 있고, 정확하게 D칸만 움직일 수 있다.

위의 두 가지 방법을 이용해서 백은진이 집에 돌아오는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오. 꼭 한 가지 방법만 사용해야 되는것이 아니고, 두 가지 방법을 적절히 조합해서 가장 빠른 시간을 구하는 것이다.

문제풀이

사용한 알고리즘 : 구현

(0) 생각

 2차원인걸 생각합니다.

 예를 들어 한번 점프에 1씩 이동하고 (1,1) 에서 (0,0) 으로 간다고 하였을 때, 2번의 점프로 정확하게 갈 수 있습니다.

 즉, 한번 점프보다 남은 집까지의 거리가 작으면, 꺾어서 2번 점프로 갈 수 있습니다.

(1) 코드 11~12

 일단 그냥 걸어가는 시간을 정답으로 잡아놓습니다.

(2) 코드 13~16

  집까지 도착하기 전 일직선으로 최대 몇 번의 점프를 할 수 있는지 구하고, 이후 남은 거리를 구합니다.

(3) 코드 18~23

 0번의 점프를 할 수 있는 경우,

    1. 일직선으로 1번 점프 후, 지나친 거리를 되돌아 오는 경우

    2. 꺾어서 2번 점프만에 가는 경우

 를 생각해줍니다.

(4) 코드 24~29

 과정 (3)의 경우가 아닌, 일직선으로 점프를 할 수 있는 경우,

    1. 최대 점프 한 후 남은 거리 걸어가는 경우

    2. 최대 점프 + 점프 한번 더 해서 꺾어 가는 경우

 를 생각해줍니다.