백준 1011. Fly me to the Alpha Centauri

https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

 

시작위치, 종료위치는 상관없고 남은 거리 갖고 생각하면 된다.

x가 0, y가 30이라면 총 이동해야하는 거리는 30이다.

 

재귀를 이용해 풀었는데 

파라미터로 남은거리, 바로 전 이동한 거리, 이동횟수를 받았다.

내가 이동할수 있는 경우의 수는 최대 3가지로

바로 전 이동한거리-1, 바로전 이동한 거리, 바로전 이동한거리+1 이다. (값이 0이하라면 이동의 의미 없으므로 제외하면된다)

 

마지막 도착 직전에 1만큼 이동해서 도착해야 한다.

이 말은 속도를 늘리다가 어느 지점에서는 속도를 1씩 줄여야 한다는 의미다.

그럼 언제 부터 속도를 줄여야 하는지를 어떻게 판단할수 있을까? 

만약 내가 4만큼 이동해서 현재 위치에 도착했다면, 이제 내가 이동할수있는 거리는 3,4,5 일 것이다.

가장 멀리 가는 범위인 5만큼 이동하고 이제부터 속도를 줄인다고 하면 이동 거리는 5 + 4 + 3 + 2 + 1 = 15가 될것이다. 

만약 남은 거리가 15이상 이라면 5만큼 이동해도 무방하다. 

하지만 15이하라면 5만큼 이동한 순간 마지막에 1만큼 이동해 도착할수가 없다.

이럴 경우 다음으로 멀리 이동하는 경우인 4만큼 이동, 안된다면 3만큼 이동하면 된다.

 

그렇다면 매번 이동할 거리 m + m-1 + m-2 ... 1 까지 더해봐야하는데 일일히 더하면 시간복잡도가 확 올라가고 등차수열의 합공식으로 구해보면 된다.

등차수열의 합 공식: 1 + 2 + ... + n-1 + n  =  (n * (n+1)) / 2 

 

참고로 등차수열을 합하는 과정에서 int 범위를 벗어날수 있다.