[백준] 1011 - 나를 알파 센타우리로 보내줘

문제: www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

 

 

어찌 되었든

 

1 2 3 4 5 ··· 5 4 3 2 1 이런 식으로 이동해야 할 것 같다.

 

1 + 2 + 3 + ··· + n + n-1 + n-2 + n-3 + ··· + 3 + 2 + 1 = n^2 이므로

 

이동해야 하는 거리 D에 대하여 n^2 <= D <= (n+1)^2 을 만족하는 n을 찾자.

 

만약 D가 (n+1)^2 쪽으로 심하게 치우쳐 있으면 아예 D를 넘긴다음에 뒤로 가는게 더 빠를 수도 있을 것 같다.

 

일단 그런 경우가 있는지 확인해볼 것이다.

D = (n+1)^2 - 1 = n^2 + 2n 이라고 가정하자.
그러면 뒤로가는 경우 최소이동횟수는 2n+3 이다.
뒤로가지 않는 경우는 2n+1 이다.

글이 너무 길어질까봐 위에서 계산과정과 중간에 있어야 할 증명들은 생략했다.

 

어쨋든 우리는 뒤로가야하는 경우는 존재하지 않는다는 것을 알았다.

 

또한, 위의 확인과정에서 n^2 <= D <= (n+1)^2 이면 최소이동횟수는 그냥 2n-1 ~ 2n+1이라는 것을 알았다.

 

D = n^2 + 2n = 1 + 2 + 3 + ··· + n + n + n + n-1 + n-2 + n-3 + ··· + 3 + 2 + 1 이므로

 

최소이동횟수가 2n+1이 나온 건데, 위 식의 우변과 좌변에 같은 수를 빼도 좌변의 n이 더 작은 어떤 수로 변할 뿐,

 

덧셈 기호의 수는 변하지 않기 때문이다.

 

다만 n이 0으로 변해버리면 최소이동횟수가 줄어든다. 그래서 2n-1 ~ 2n+1라는 범위가 나오는 것이다.

 

어쨋든 이런 아이디어를 통해 문제를 풀면 될 것 같다.