백준 1011번 규칙찾기/Fly me to the Alpha Centauri

문제: Fly me to the Alpha Centauri

문제풀이에 도움받은 글들

풀이 정리해보았습니다, (xaemin 님)
★★★ 필독!!! ★★★ Fly Me FAQ ★★★ 안 읽으면 후회! ★★★(jh05013 님)
Baekjoon online judge slack

우현이의 공간이동 장치는 시작지점에서 1광년만큼 이동할 수 있으며, 이후 이동거리를 유지하거나 혹은 1만큼 증감이 가능하다. 즉 두 번째로 이동할 때는 1광년만큼 이동하거나, 2광년만큼 이동할 수 있다. 또, y지점에 도착하기 전까지는 이동거리를 점점 감소시켜서, 최종적으로 1광년만큼 움직여 y지점에 도착해야한다. 나는 이 부분을 제대로 이해하지 못해서 안그래도 오래 걸리는 시간이 더더욱 오래 걸렸다.

문제의 목적은 x지점에서 y지점으로 이동할 때 공간이동 장치를 최소한으로 작동시키는 방법이다. x지점과 y지점의 좌표가 주어졌으므로, x지점과 y지점 사이의 거리는 y-x로 구할 수 있다. 예제 입력과 출력을 살펴보자. y-x값이 3일때는 3번, 4일때는 3번, 5일때는 4번 이동해서 y지점에 도착할 수 있다. 거리를 기준으로 정리하면 다음과 같다.

• 3만큼 이동할 때는 1, 1, 1와 같은 방식으로 이동하여 y지점에 도착할 수 있다.
• 4만큼 이동할 때는 1, 2, 1와 같은 방식으로 이동하여 y지점에 도착할 수 있다.
• 5만큼 이동할 때는 1, 2, 1, 1 혹은 1, 1, 2, 1과 같은 방식으로 이동하여 y지점에 도착할 수 있다.

3, 4만큼 이동할 때는 3번 이동해서 y지점에 도착할 수 있었다. 하지만 5만큼 이동할때는 4번 이동해야 y지점에 도착할 수 있었다. 그렇다면 이동횟수에 따라 정리해보면, 다음과 같다.

• 1번 이동(1): 최대 1만큼 이동할 수 있다.
• 2번 이동(1, 1): 최대 2만큼 이동할 수 있다.
• 3번 이동(1, 1, 1)(1, 2, 1): 최대 3만큼 이동할 수 있다.
• 4번 이동(1, 1, 1, 1)(1, 2, 1, 1)(1, 1, 2, 1)(1, 2, 2, 1): 최대 6만큼 이동할 수 있다.

n번 이동했을 때 최대한 이동할 수 있는 거리를 구할 수 있음을 알 수 있다. 이동횟수에 따른 최대거리를 구하면 다음과 같이 정리할 수 있다.

이동횟수	최대 이동거리	이동방법
1	1	1
2	2	1 1
3	3	1 1 1
4	6	1 2 2 1
5	9	1 2 3 2 1
6	12	1 2 3 3 2 1
7	16	1 2 3 4 3 2 1
…	…	…

우선 이동횟수가 3 이하일 경우에는, 최대 이동거리가 이동횟수와 동일하다는 것을 할 수 있다. 이동횟수가 짝수일때는 정확히 절반으로 나뉘어지므로, n번 이동할 때 최대 이동거리는 sum(n/2)2임을 알 수 있다. 또한 이동횟수가 홀수일때는 가운뎃값을 기준으로 대칭이 됨을 알 수 있다. (n-1)/2+1만큼 증가하다가 다시 감소하고 있으므로, 최대 이동거리는 sum((n-1)/2)2+(n-1)/2+1임을 알 수 있다.

위의 내용을 바탕으로 n번 이동할 때 갈 수 있는 최대 이동거리를 구해보자.

convertStepToMaximumDistance(step) {
  if (step이 3이하일 경우) return step;
  if (짝수일 경우) {
    return sum(step/2)*2;
  } else {
    return sum((step-1)/2)*2+((step-1)/2)+1;
  }
}

위의 수도코드를 통해서 n번 이동했을 때 최대 이동거리를 구할 수 있다. 따라서 x지점과 y지점 사이의 거리가 n번 이동했을 때의 최대 이동거리보다 큰 경우를 만족하는 n값을 찾으면, x지점에서 y지점으로 이동할 때 최적의 이동횟수를 구할 수 있다.

내가 작성한 코드는 아래와 같다.

#include <stdio.h>

long long sigma_n(long long param_n) { //sum(n), n까지의 합을 반환하는 함수
    return (param_n*(param_n+1))/2;
}

long long convertStepToDistance(int param_step) { //이동횟수가 주어졌을 때 최대 이동거리를 반환하는 함수
    long long distance = 0;

    if(param_step <= 2) {return param_step;}

    if(param_step%2==0) {
        distance = sigma_n(param_step/2)*2;
    } else {
        distance = sigma_n((param_step-1)/2)*2+((param_step-1)/2)+1;
    }

    return distance;
}

int main() {
    long long input_x=0, input_y=0;
    long long distance=0;
    long long count_move=1, count_input=0;
    long long index=0;

    count_input=0;
    scanf("%lld", &count_input);

    for(index=0; index<count_input; index++) {
        input_x=0, input_y=0, count_move=1;
        scanf("%lld %lld", &input_x, &input_y);

        distance = input_y-input_x;

        //최대 이동거리가 x지점과 y지점 사이의 거리보다 큰 값을 만족하는 n값을 찾는다.
        while(distance > convertStepToDistance(count_move)) {
            count_move++;
        }

        printf("%d\n", count_move);
    }

    return 0;
}

---

푸는 속도가 너무 안늘어서 큰일이다 ‘ ㅅ’
언제쯤되면 하루에 몇문제씩 풀 수 있을까.

​