BOJ 1011 Fly me to the Alpha Centauri

x지점에서 y지점으로 이동할 때, 이동횟수의 최소값을 구하는 문제인데, 중요한 규칙이 하나 있다. 일단 처음에는 1밖에 못움직이고, 이전에 k만큼 움직였다면 다음엔 k-1, k, k+1중 하나로 움직일 수 있고, 마지막에 y에 도달할 때는 1만큼 움직여서 y에 도달해야 한다. 즉 y-1에서 y로 도달해야 한다. 또 그러기 위해서는 y-1까지 오는 움직임은 y-2에서 1만큼 오거나 y-3에서 2만큼 오는 두 가지 경우 밖에 없을 것이다.

x => 1 => x+1 => .... => y-1 => 1 => y
x+1 지점부터 1만큼 갈지 2만큼 갈지 결정하는 것부터 시작해서 y-1에 도착하면 1만큼 갈 수 있게 y-1에 적절한 경로를 거쳐 도착해야 할 것이다.
dp로 해보면 괜찮을 것 같은데 x, y의 범위가 2의 31제곱-1 까지이다... 무려 20억이 넘는 수...

직접 해보면 1 다음에는 1, 2로 움직일 수 있고, 그 다음에는 1-1, 2 / 2-1, 2, 3 ... 이렇게 1보다 큰 수들은 모두 3가지로 나눠질 수 있다. 대략 3의 n제곱 개... 엄청 많은 경우의 수이다.

아 좀 더 생각해보니, dp를 이용하거나 모든 경우를 다 해볼 필요가 없어보이는 것이... 최소로 움직여야 하고, 그리고 시작 움직임과 끝 움직임이 1이여야 한다. 또한 한 번에 늘리거나 줄일 수 있는 거리도 1밖에 안된다. 즉 일단은 1부터 시작해서 최소로 움직이려면 1, 2, 3, 4... 이렇게 움직이는 거리를 늘려나가야 하는데 무작정 늘리면 안되는 것이 마지막 움직임은 1이 되야하므로 어느정도까지 늘렸다가 줄여야 하는데, 줄일 때는 한 번에 1씩밖에 못 줄인다. 그렇기 때문에 늘리는 것은 중간지점까지 밖에 못 늘리고(중간 지점을 넘어서까지 늘리면 마지막에 1로 움직일 수 없다), 중간지점까지 최대한 1씩 늘렸다가 중간에서 1씩 줄이는 것이 최소한으로 움직일 수 있는 방법이 될 것이다.
 음 처음엔 dp인가... 모든 경우를 다 고려해 봐야하나.. 했는데 이렇게 시작과 끝의 움직이는 거리 조건이 1로 주어진 것이나 한 번에 늘리거나 줄일 수 있는 거리가 1밖에 안된다는 점.. 그리고 최소로 움직이는 횟수를 구해야 한다는 점들 때문에 이렇게 풀 수 있게 되는 것 같다. 멋있는 문제다.

자 그럼 구현은 어떻게 할까? x, y가 주어지면 y-x값을 가지고 작업을 시작한다.
일단 1부터 n까지의 합은 n*(n+1)/2로 나타낼 수 있는데 n이 5만(50000)일 때, 즉 1부터 50000까지의 합이 1,250,025,000 으로 12억이 넘는다. 2의 31제곱이 약 22억정도 이므로 대충 50000까지의 누적합만 이용해도 충분하다.
50000까지의 누적합을 미리 구해놓고(그냥 n*(n+1)/2), 양쪽에서 1, 2, 3... 이렇게 움직인다고 생각하면
y-x >= psum[x]*2 인 최대의 x를 찾는다. 만약 y-x=psum[x]*2라면 답은 x*2가 될 것이고, 아니라면 음... 여러가지 경우가 생길 수 있어보인다. 고민하다가 맞은 사람 목록을 봤는데, 코드들이 상당히 짧다. 질문 게시판도 봐야겠다. 다른 분들의 글을 대충 봤는데, 규칙을 이용하거나 수식으로 간단하게 푸시는 것 같다. 좀 더 고민해 봐야겠다.

결국 검색을 통해 isac322님의 코드를 봤다. 와 엄청 간단하고 짧고... 코드를 보면서 어떻게 이렇게? 라는 생각이 들었지만 잘 생각해보니 맞다.... 아 난 왜 이런 생각을 못했을까라는 생각도 들지만, 그 전에 다른 방법으로도 짠 사람들 많던데 난 다른 방법도 생각 못했다.

접근은 위에서 생각한 것과 비슷하다. y-x >=psum[x]*2 인 최대의 x를 찾는데, 문제가 되는 부분은 y-x > psum[x]*2일 때, (y-x)-psum[x]*2값을 어떻게 처리하냐였다. 여기서 어떻게 할 것인가? (y-x)-psum[x]*2==k라고 하자. k값은 psum[x+1]*2보단 (x+1)*2보단 작은 값일 것이다. 만약 k값이 psum[x+1]값 (x+1)과 같다면 x*2+1이 답이될 것이다. 여기까지는 쉽다. 자 이제 잘 생각해야 한다. 만약 k값이 psum[x+1]값 (x+1)보다 작은 경우와 k값이 psum[x+1] (x+1)보다 큰 경우가 있는데 둘 다 결론부터 말하면 답은 각각 x*2+1, x*2+2가 된다.

k값이 psum[x+1] (x+1)보다 작은 경우부터 보자. 지금 상태를 보면 k값을 중간에 놔두고, k값 양쪽에서 1+ 2+ 3.+..+x 만큼 온 상태이다. k값이 x-1이라면 가능하겠지만, x와 차이가 크다면? 그럼 처음부터 모든 경우를 해봐야 하는 것 아닐까? 아니다. 그럴 필요 없다. k이전 값이든 이후 값이든 하나를 기준으로 잡자. k 이전 값들을 기준으로 잡고 k값이 x값과 차이가 1이 나도록 이전 값들을 다 1씩 줄인다. 만약 이전 값중에 3개의 값만 1씩 줄이면 k값은 3이 늘어날 것이다. 맨 처음 시작 값인 1은 못 줄인다해도 2부터 줄이기만 해도 x-1만큼의 길이를 확보할 수 있다. 즉 k값이 최대 x-1만큼 늘어날 수 있다는 것이다. 만약 양 쪽다 조정한다면 더 많이 늘어날 수 있지만 그럴 필요는 없고, 만약 k가 1이라해도 x-1만큼 늘어나면 x가 된다.
그래서 k도 수용할 수 있게 되고, 결국 답은 2*x+1이 되는 것이다.

그리고 k값이 psum[x+1] (x+1)보다 큰 경우도 마찬가지다. (설명 생략)

왼쪽, 오른쪽 수와는 0 또는 1이 차이나야 해서 1+2+3...+x인 상태에서는 2부터 x까지 1씩 줄여줌으로써 x-1만큼을 늘려줄 수가 있다.(물론 더 늘릴 수도 있지만 k가 1로 가장 작은 경우에도 x-1만큼만 늘리면 된다)

그리고 이렇게 하면 최소값이 될까? 일단 1+2+3+..이렇게 온 것 자체는 최소값의 페이스대로 한 것이다. 그리고 거기서 1을 더해준 것인데, 최소값이 될 수 밖에 없는 게, 최소값의 페이스 했는데도 k가 남았다면 어떻게 오든지 간에 (최소값의 페이스의 경우) + 1보다 작을 수가 없다.

비록 내가 생각하지는 못했지만 좋은 깨달음을 얻었고, 멋진 문제같다.
그리고 github에 isac322님이 공개해주신 코드를 보고 깨달음을 얻을 수 있었다.
구현해 봐야겠다.

주의할 점으로 psum[x]*2 부분에서 int 형 범위를 넘어갈 수 있기 때문에 long long으로 처리해야 한다.
AC를 받았다.