가능하다면 처음에는 /처럼 계속 Step을 1씩 증가시키며 올라가다가, 최고점에서부터 1씩 감소시켜서 내려오는 게 낭비 없이 최선일 겁니다.

예를 들어서 거리 9만큼 떨어진 지점을 가려 하면 [1, 2, 3, 2, 1] 순서로 이동하는 것이 좋겠죠.

음... 이걸 편의상 길이 5짜리 오르락내리락 순열이라 하죠 뭐. 길이 6짜리 오르락내리락 순열이라면 [1,2,3,3,2,1]이 되겠죠?

근데 생각해보면 여기서 가장 큰 step으로 뛴 곳에서 1만큼 덜 뛰도록 하면 최종 결과도 1칸씩 줄어들며 중간에 모순도 생기지 않습니다.

9 : [1,2,3,2,1]
8 : [1,2,2,2,1]
7 : [1,1,2,2,1]
6 : [1,1,1,2,1]
5 : [1,1,1,1,1]

음.. 물론 5와 6은 각각 [1,1,2,1]과 [1,2,2,1]으로 거쳐가는 것이 더 좋긴 합니다. 아무튼.. 기본적인 아이디어는 이겁니다. 오르락내리락 순열의 최대값을(즉, (순열 길이+1) / 2) 알면, 어디서부터 어디까지를 갈 수 있는지 알 수 있다는 거에요.

그럼 순열의 최대값을 기준으로 해당 거리가 어느 구간에 속하는지를 알면 되는데, for문 돌려도 되겠지만 x=0, y = 2^31-1인 경우 sqrt(2^31)이 46340 근처니까 대략4만번 이상 돌겠죠? 이진탐색으로 찾습니다.

#include<iostream>
#include<algorithm>
using namespace std;


// 1+2+3+...+maxv+(maxv-1)+....+3+2+1 = maxv(maxv+1) - maxv = maxv^2
long long when_odd_length(long long maxv){
    return maxv * maxv;
}

long long when_even_length(long long maxv){
    return maxv * (maxv + 1);
}

int steps(long long dist){
    int min = 1;
    int max = 2 << 17;
    int mid;

    while (min <= max){
        mid = (min + max) >> 1;     
        if(dist <= when_even_length(mid-1)){
            max = mid - 1;
        }
        else if(dist > when_even_length(mid)){
            min = mid + 1;
        }
        else if(dist <= when_odd_length(mid)){
            return mid*2-1;
        }
        else {
            return mid*2;

        }
    }
    return -1;
}


int main(){
    int testcase_cnt;
    cin >> testcase_cnt;

    while(testcase_cnt-- > 0){
        int x, y;
        cin >> x >> y;
        cout << steps(y-x) << endl;
    }
    return 0;
}

영역이 n**2가 된다는 걸알면 쉬운 문제네요. 루비입니다.

def steps(a, b)
  ((a - b).abs**0.5).ceil
end

무식한 방법으로 한번 해 봤습니다.

step은 아래와 같이 변화합니다.

1
1,1
1,1,1
1,2,1
1,2,1,1
1,2,2,1
1,2,2,1,1
1,2,2,2,1
1,2,3,2,1
1,2,3,2,1,1
1,2,3,2,2,1
1,2,3,3,2,1

요 순열을 그냥 그대로 프로그램에 옮겨 보았습니다.

파이썬입니다.

def step(start, end):
    gap = end-start
    result = [1]
    while True:
        if sum(result) == gap:
            break
        found = False
        for i, s in enumerate(result):
            if i==0:  # first
                continue
            elif i==len(result)-1:  # last
                continue
            cur = s+1
            before = result[i-1]
            after = result[i+1]
            if abs(cur-before) <= 1 and abs(cur-after) <= 1:  # ok
                result[i] = cur
                found = True
                break

        if not found:
            result.append(1)

    #print result
    return len(result)

print step(45,48)
print step(45,49)
print step(45,50)
print step(1, 2**16)

y값이 2¹⁶ 까지는 금방 나오지만 2³¹ 은 감감 무소식이네요..

제가 최근에 해결한 fly me to the alpha centauri 라는 문제랑 비슷하네요. 우선 x,y의 범위가 상당히 크므로 simulate하는 방법으로 시간이 오래 걸립니다. 사실 문제의 조건을 만족하면서 도착점에 도달하려면 steps가 1씩 늘어나는 경우는 여태까지 이동한 거리들이 "대칭"을 이룰때입니다. i.e. 1, 11, 121, 1221, 12321, 123321, 1234321, 12344321, 123454321,... 의 경우고 이때는 거리들의 값은 1,2,4,6,9,12,16,20,25,...입니다. 여기서 유추할 수 있는 패턴은 어떠한 i에 대해서 만약 x,y의 거리 d가 i*i < d <= i*(i+1)을 만족하면 최소 2*i번의 이동이 필요하고, i*(i+1) < d <= (i+1)*(i+1) 을 만족하면 최소 2*i+1번의 이동이 필요합니다. 따라서 임의의 거리 d가 주어지면 최대 sqrt(2^31) < 10^5의 범위에 속하는 i만 확인하면 되므로, 고속으로 문제를 해결할 수 있습니다. 아래는 제 C++ 코드입니다.

#include <iostream> 
#include <cstdlib> 
#include <cstdio> 
#include <cmath> 
#include <cstring> 
#include <algorithm> 
using namespace std; 

#define INF 2147483648

typedef long long ll;  

int main(){
    int t; 
    scanf("%d",&t); 
    while (t--){
        int x,y; 
        scanf("%d %d",&x,&y); 
        if (x == y) printf("0\n"); 
        else if (y-x == 1) printf("1\n"); 
        ll d = y-x;  
        ll limit = (int)sqrt(INF)+1; 
        for (ll i = 1; i <= limit ;i++){ 
            if (d > i*i && i*(i+1) >= d){ 
                printf("%lld\n",2*i); break; 
            }else if (d > i*(i+1) && (i+1)*(i+1) >= d){
                printf("%lld\n",2*i+1); break; 
            }
        }
    }
    return 0; 
}

by phantom

def func1(n): //n을 움직인 횟수라고 했을때 
    if n%2 == 0:
        return n*(n+2)/4
    else:
        return [(n+1)/2]**2   // 최대한 움직일 수 있는 거리를 반환

이 함수를 역순으로 하면 

def answer(i):
    from math import sqrt
    t=int(sqrt(i))
    if sqrt(i).is_integer():
        return 2*t-1
    elif i >t*(t+1):
        return 2*t+1
    else:
        return 2*t

answer(2**31)=92681

import math
aaa=int(eval(input()))
bbb=int(eval(input()))
ccc=abs(aaa-bbb)
k=1
t=math.floor(math.sqrt(ccc))
ccc-=t**2
print(math.ceil(ccc/t)+2*t-1)

오메가(1)나오네요

파이썬입니다. 스탭의 형태는 기본적으로 증가후 감소하는 피라미드형이며 거기에 중복되는 수를 더하는 식입니다

스탭      실제간격
[1]          1
[11]         2
[121]        4
[12321]      9
[1234321]   16

가령 '5'의 스탭을 구하려면 해당 값(간격)은 [121]스탭과 [12321]스탭 사이 영역에 있으므로 먼저 [121] 스탭을 구한뒤 '중복되는 값'을 더해 [1211] 이런 식으로 연장하면 됩니다.

저는 '해당 값이 어느 영역에 속하는지를 구하는 메소드'와 그것에 '필요한 만큼 중복값을 더하는 메소드'로 분리하여 풀어봤습니다.

class step:
    def py(self, n):
        step = 3
        incr = 2
        length = 4

        while n >= length:
            step += 2
            incr += 1
            length += (incr * 2) - 1

        lst = [step - 2, incr - 1, length - ((incr * 2) - 1)]
        return lst

    def act(self,x,y):
        length = y - x
        step = 0
        big_numb = 0
        left_length = 0

        if length in range(4):
            return length
        elif length > 3:
            step = self.py(length)[0]
            big_numb = self.py(length)[1]
            left_length = length - self.py(length)[2]

        while left_length != 0:
            if left_length >= big_numb:
                left_length -= big_numb
                step += 1
            else: big_numb -= 1
        return step


test = step()
print test.act(2,6)
print test.act(2,7)

모두들 알고 계시겠지만

자연수 1부터 n까지의 합 : n*(n+1)/2

자연수 1부터 n-1까지의 합 : n*(n-1)/2

1,2,…,n-1,n,n-1,…,2,1의 합 : n*n

따라서 거리 d가 주어지면, 일단 그 수 이하의 최대의 n²를 구합니다. 현재 단계는 2n-1입니다.

나머지가 있다면 n으로 나누고 몫을 단계에 더합니다. (n길이의 단계가 최대 길이의 단계로 이미 있습니다.)

또 나머지가 나오면 단계 수에 1을 더해줍니다. (n보다 작은 길이의 단계도 이미 있습니다.)

입출력부는 생략합니다. 주 정수 사이의 거리를 구해서 호출하면 됩니다.

Perl

use integer;

sub i{
    my $i=shift;
    my $s=sqrt($i);
    my $r=$i-$s**2;
    my $n=2*$s-1;

    if ($r>0){
        my $e=$r/$s;
        $e*$s < $r ? $n+=$e+1 : $n+=$e
    }
    return $n;
}

    static void exce51()
    {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] arr = new int[n][2];

        for (int i = 0; i < n; i++)
        {
            arr[i][0] = scan.nextInt();
            arr[i][1] = scan.nextInt();
        }

        for (int i = 0; i < n; i++)
        {
            int p = 1;
            int gap = arr[i][1] - arr[i][0];

            while (p * p < gap)
                p++;

            if (p * p - p >= gap)
                System.out.println(2 * (p - 1));
            else
                System.out.println(2 * p - 1);
        }

    }

기본 아이디어는 최단경로는 1,2,3,,,n-1,n,n-1.n-2,,,,3,2,1 요런식으로 된다고 가정하였습니다. 이 경우 총 합(= 해당 경로로 이동하는 거리)는 n^2이 됩니다. (1~n합 + 1~(n-1)합 = 2(1~n합) - n = 2(n(n+1)/2) -n = n^2 + n - n = n^2) 두 점 사이 거리가 n^2보다 작아지는 n의 최소값을 찾아내면 꼭지점 부터 규칙에 위배되지 않도록 1씩 줄여나가면 해당 거리에 해당하는 값이 나오게 되므로 2n -1 이 이동 횟수입니다. ex)두점사이거리 : 7 n 은3(1 2 3 2 1) -> ( 1 2 2 2 1) -> (1 2 1 2 1) 7칸 이동 하지만 만약에 두점 사이 거리가 n^2 - n 보다 작거나 같다면 피라미드의 꼭지점을 빼도 됩니다. ex) 두점사이거리 : 5 n은 3 (1 2 3 2 1) n^2 - 3 = 6 > 두점사이 거리 -> (1 2 2 1 - > 1 1 2 1 5칸 이동)

C#으로 작성했습니다.

using System;

        public int CountSteps(int n)
        {
            var sqrt = Math.Sqrt(n);
            if (sqrt%1 == 0) return (int) (sqrt*2 - 1);
            var max = (int) Math.Floor(sqrt);
            var count = max*2 - 1;
            var remainder = n - (max*max);
            for (int i = max; remainder > 0; i--)
            {
                if (i*2 <= remainder)
                {
                    remainder -= i*2;
                    count += 2;
                }
                if (i <= remainder)
                {
                    remainder -= i;
                    count++;
                }
            }
            return count;
        }

파이썬 2.7입니다.

def steps(x,y):
    m = int((y-x)**0.5)
    r = y-x-m*m
    return 2*m-1 + r/m + (1 if r%m else 0)

k 단계로 갈 수 있는 최대 거리는 k = 2a - 1 일 때 a * a 가 됩니다. (a = 1, 2, 3 .... )

또, 두 수의 차이가 점점 커질 때, 자연수 n에 대해 n * n 혹은 n * (n - 1) 이 되는 시점에 단계의 개수가 바뀌게 됩니다.

이 규칙을 이용해서 두 수의 차이로부터 단계의 수를 산출해낼 수 있습니다.

def do(a, b):
    gap = abs(a - b)
    x = gap ** 0.5
    if int(x) == x: 
        return int(x) * 2 - 1
    elif gap > int(x) * int(x + 1):
        return int(x) * 2 + 1
    else:
        return int(x) * 2

# test
for b in range(46, 51):
    print(45, b, do(45, b))

print(do(1, 2**31))

Ruby

s=b-a일때, 최대거리는 (s*(s+2)+s%2)/4.

step = ->a,b,n=b-a { s=(n**0.5).to_i; 2*s+(n**0.5==s ? -1 : n>s*s+s ? 1:0) }
steps = ->n=gets.to_i { puts (1..n).map {gets.chop.split.map &:to_i}.map &step }

Test

expect(step[45,48]).to eq 3
expect(step[45,49]).to eq 3
expect(step[45,50]).to eq 4
expect(step[0,2**31]).to eq 92681

#=> stdin/stdout test
$stdin = StringIO.new("3\n45 48\n45 49\n45 50\n")
expect { steps[] }.to output("3\n3\n4\n").to_stdout

Output

#=> steps[]
3
45 48
45 49
45 50
3
3
4

java 저도 무식한 방법으로... 1. step 1씩 증가 할수 있는 max 값을 구하고. 2. step 1이 될때까지 계속 감소. 3. step 이 1이면 나머진 모두 1.

각 단계는 증가한 step 에서 -1씩 했을 때 마지막에 1이 오는지 검사. 2^30까진 그나마..나오네요

private static void Test() {
        int data1 = 45;
        int data2 = 50;
        getCount(data2 - data1);
    }

    private static void getCount(int max) {
        int Count = 1;
        int index = 1;
        int current_ori = index;

        System.out.println("index = " + index + " Count = " + Count);
        while (true) { // 증가 가능한 max 까지 step 증가
            int current = verifyOver(current_ori, index + 1);
            if (current <= max) {
                index++;
                current_ori += index;
                Count++;
                System.out.println("index = " + index + " Count = " + Count);
            } else {
                break;
            }
        }
        while (index != 1) { // step 이 같거나 감소 할 때
            int current = verifyOver(current_ori, index);
            if (current > max) {
                current = verifyOver(current_ori, index - 1);
                if (current <= max) {
                    index--;
                }
            }
            System.out.println("index = " + index + " Count = " + Count);
            current_ori += index;
            Count++;
        }
        while (current_ori + index <= max) { // step 1 이 되었을 때 처리
            current_ori++;
            Count++;
            System.out.println("index = " + index + " Count = " + Count);
        }

    }

    private static int verifyOver(int current_ori, int index) {
        int current = current_ori;
        for (int i = index; i > 0; i--) {
            current += i;
        }
        return current;
    }

#include <stdio.h>
#include <stdlib.h>

void main() {
    int T = 0;
    scanf("%d", &T);
    int  *count = (int*)  malloc (sizeof(int)  * T);
    bool *b     = (bool*) malloc (sizeof(bool) * T);
    for(int i = 0;i<T;i++) { 
        b[i] = false;
        count[i] = 0;
    }
    for(int i = 0;i<T;i++) {
        int low  = 0;
        int high = 0;
        scanf("%d %d", &low, &high);
        int interval = 1;

        while(interval < high-low) {
            low  = low  + interval;
            high = high - interval;
            if(high < low) 
                b[i] = true;
            count[i]++;
            interval++;
        }

        if(b[i])
            count[i] = count[i]*2;
        else
            count[i] = count[i]*2+1;
    }
    for(int i=0;i<T;i++) {
        printf("%d\n", count[i]);
    }
}

_list = [list(map(int,input().split(' '))) for x in range(int(input()))]

for val in _list:
    p = [x for x in range(val[0],val[-1]+1)]
    step,c,count = 0,0,0
    while p[step] != p[-1]:
        if step < (p[-1]-p[step]) / 2:
            c += 1
            step += c
        elif p[step]-p[0] == p[-1]-p[step] and (p[-1] - p[0]) % 6 == 0:
            step += c
        else:
            c -= 1
            step += 1
        count += 1
    print(count)

#### 2017.02.02 D-385 ####

import java.util.Scanner;

public class Steps {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < sc.nextInt(); i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            System.out.println(recursive(b - a, 1));
        }
    }

    private static int recursive(int gap, int i) {
        if (gap > i * 2) {
            return 2 + recursive(gap - i * 2, i + 1);
        } else {
            return gap > i ? 2 : 1;
        }
    }
}

파이썬 3.6

"""
아이디어>
 1) x ,y 사이의 길이(length)가 2보다 작거나 같을 경우 해당 최소 단계는 length와 같습니다.
 2) length가 2 초과이면 최소 단계수는 2 이상이며, 처음과 끝 단계를 제외한 길이(length-2)에서는 최대 길이(2)로 이동이 가능하여 (length-2)/2단계가 추가로 필요하고,
 3) (length-2)가 2의 배수가 아닐 경우에는 (length-2)/2 + 1 단계가 추가로 필요합니다.(처음과 마지막 단계는 1이어야 하므로)
"""
def inputdata(data_list):
    n = int(input("n = "))
    for i in range(n):
        x=int(input("data%d_x = "%(i+1)))
        y=int(input("data%d_y = "%(i+1)))
        data_list.append([x,y])
    print("\n")

def steps(data):
    step, length = 0, data[1]-data[0]
    if length  > 2:
        step += 2
        if length - 2 <= 2 :
            step += 1
        elif length - 2 > 0 and (length - 2)%2 == 0:
            step += (length - 2)//2
        else:
            step +=((length-2)//2 + 1)           
    else:
        step = length
    print(step)   

if __name__ == "__main__":
    data_list =[]
    inputdata(data_list)
    for data in data_list:
        steps(data)

*결과값

n = 3
data1_x = 45
data1_y = 48
data2_x = 45
data2_y = 49
data3_x = 45
data3_y = 50


3
3
4

import math
def step(m ,n):
    if m > n:
        (m, n) = (n, m)
    if n == m or n-m == 1 or n-m == 2:
        return n-m
    elif n-m <= math.ceil(math.sqrt(n-m))*math.ceil(math.sqrt(n-m)-1):
        return 2*math.ceil(math.sqrt(n-m)-1)
    else:
        return 2*math.ceil(math.sqrt(n-m)-1)+1

n = int(input())
l = [list(map(int, input().split(' '))) for i in range(n)]
for i in l:
    print(step(i[0], i[1]))

import java.util.Scanner;

public class Steps {

    public static int solve(int head, int rear){

        int count = 0; // 단계수
        int level = 1; // 현재 단계
        int order = 0; // true면 앞 먼저, false면 뒤 먼저
        while(true){
            if(head == rear){
                break;
            }

            //rear > head 인경우
            int hrDistance = rear - head;

            if(hrDistance < level){
                level--;
            }

            if(hrDistance >= level && order % 3 == 0){
                head += level;
                count++;
                order++;
                continue;
            }
            if(hrDistance >= level && order % 3 == 1){
                rear -= level;
                count++;
                order++;
                continue;
            }
            if(hrDistance >= level && order % 3 == 2){
                level++;
                order++;
                continue;
            }

        }

        return count;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);

        int testCase = Integer.parseInt(sc.nextLine());

        for(int i=0; i< testCase; i++){
            String[] inputLine = sc.nextLine().split(" ");
            int head = Integer.parseInt(inputLine[0]);
            int rear = Integer.parseInt(inputLine[1]);

            int count = solve(head, rear);

            System.out.println(count);
        }
    }

}

// 자바입니다
머리 딸려서 규칙 찾으려고 메모장에다가 노가다하면서 찾았네요. 
길이가 n (자연수)의 제곱일 때 단계수가 대칭된다는 걸 알수 있어요. 그걸 코드로 옮기면

public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            String[] str = br.readLine().split(" ");
            long x = Long.parseLong(str[0]);
            long y = Long.parseLong(str[1]);
            long distance = y - x;
            if (distance == 1) {
                System.out.println(1);
            } else if (distance == 2) {
                System.out.println(2);
            } else {
                int n = 1;
                int range1 = 0;
                int range2 = 0;

                while (true) {
                    n++;
                    range1 = n * n - (n - 1);
                    range2 = n * n + n;
                    if (range1 <= distance && distance <= n * n) {
                        System.out.println(2 * n - 1);
                        break;
                    } else if (n * n < distance && distance <= range2) {
                        System.out.println(2 * n);
                        break;
                    }
                }
            }
        }
    }
// 일케 됩니다. 루비는 신기하네요. 코드가 저렇게 짧다니

/*
0 = 0
1 = 1
11 = 2
121 = 4
1221 = 6
12321 = 9
123321 = 12
1234321 = 16
12344321 = 20

1씩 2번, 2씩 2번, 3씩 2번, 4씩 2번 이러한 규칙으로 커지고, 해당 합계 숫자는 각 스탭의 최대 거리입니다.
위의 규칙을 이용해 풀어봤습니다.
*/

import java.util.Scanner;

public class Steps {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = Integer.valueOf(sc.nextLine().trim());
        int[][] steps = new int[num][2];
        for (int i = 0; i < num; i++) {
            String[] temp = sc.nextLine().split(" ");
            steps[i][0] = Integer.valueOf(temp[0]);
            steps[i][1] = Integer.valueOf(temp[1]);
        }
        for (int i = 0; i < steps.length; i++) {
            int count = 0;
            int length = steps[i][1] - steps[i][0];
            int a = 0, b = 1;
            while (a < length) {
                a += b;
                count++;
                if (count % 2 == 0)
                    b++;
            }
            System.out.println(count);
        }
    }
}

Python

import math
x, y = map(int, input().split(' '))
dist = abs(x - y)
n = math.ceil(math.sqrt(dist))
k = n*2 - 1
if dist <= n*n - n:
    k -= 1
print(k)

양 끝은 1로 수렴하므로
1 2 ... n ...2 1 ==> n^2 기본 수열로
부족한 수는 n,...,2,1 에서 채워 넣는다

n = int(input())
inv = []
for i in range(n):
    inv.append(tuple(map(int,input().split())))

for j in map(lambda n: n if n < 4 else int(n**0.5)*2-1 if n-int(n**0.5)**2 == 0 else int(n**0.5)*2+1 if n-int(n**0.5)**2 > int(n**0.5) else int(n**0.5)*2, (i[1]-i[0] for i in inv)): print(j)

3
45 60
59 78
0 40
7
8
12

L = y -x 라 하면,

2s 단계로 갈 수 있는 최대 길이 = (1 + 2 + ... + s) * 2 = s(s + 1)

s(s + 2) <= L 이어야 하므로

sqrt(L + 1) - 1 <= s (근의 공식)

s 의 최대값을 S라 할 때

S = ceil(sqrt(L + 1) - 1) (S 는 자연수)

이고 이 떄 2S 단계로 진행한 길이는 S(S + 1) 이다.

-

2-1.

남은 길이를 R 이라 하면,

R = L - S(S + 1)

현재까지 가장 길이가 긴 단계의 길이는 S 이므로, 중간에 길이 S 인 단계를 R // S 만큼 더 반복할 수 있다.

그 후에 남는 길이를 R2 라 하면,

R2 = R - R // S

-

2-2.

R 이 S 로 나누어 떨어지지 않으면

마지막으로 길이 R2 인 단계를 한번 더 반복한다. (R2 < S 이므로)

-

1, 2-1, 2-2로부터 최소 단계 수 = 2 * S + ceil(R / S)

from math import ceil, sqrt
def min_steps(L):
    S = ceil(sqrt(L + 1) - 1)
    R = L - S * (S + 1)
    return 2 * S + ceil(R / S)

rawdata = '3\n45 48\n45 49\n45 50'
data = rawdata.split()[1:]
while data:
    x, y = int(data.pop(0)), int(data.pop(0))
    print(min_steps(y - x))

재귀함수를 사용하여 풀었습니다.

def check(f_num,c_num,num):
    if (num < 0) | (f_num < c_num):
        return 0    
    c_num +=num
    if f_num == c_num:
        return 1
    return check(f_num,c_num,(num-1)) + check(f_num,c_num,(num+1))

cir = int(input())
for i in range(cir):
    n1,n2 = map(int, input().split(' '))
    sum_num = 2
    if (n2 -n1) >=3:
       sum_num += check((n2 -n1-2),0,1)
    print(sum_num)

이 문제는 코딩문제라기보다 수학문제에 가까워 보이네요.

import math

def f(x, y):
    length = y - x
    n = math.floor(math.sqrt(length))
    k = length - n*n
    return (2*n - 1) + ((k - 1)//n + 1)

>>> f(0,2**16)
511
>>> f(45, 48)
3
>>> f(45, 49)
3
>>> f(45, 50)
4
>>> f(0, 2**16)
511
>>> f(0, 3**16)
13121

C#

숫자간의 거리를 D, 스텝의 길이를 SL이라고 할 때,

SL = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...에 대해 D = 1, 2, 4, 6, 9, 12, 16, 20, 25, 30, ...이므로,

D = floor((SL + 1)**2 / 4)의 관계를 갖는다.

https://oeis.org/A002620 수열 참조

using System;
using System.Linq;
using System.Text;

namespace CD051Cs
{
    class Program
    {
        static void Main()
        {
            int numberCases = int.Parse(Console.ReadLine());
            StringBuilder sb = new StringBuilder();
            for (int test = 0; test < numberCases; test++)
            {
                int[] testCase = Console.ReadLine().Split(' ').Select(n => int.Parse(n)).ToArray();
                sb.AppendLine(GetStepLength(Math.Abs(testCase[0] - testCase[1])).ToString());
            }
            Console.WriteLine(sb);
        }

        static int GetStepLength(int distance)
        {
            int step = 0;
            int estimatedDistance = 0;
            while (distance > estimatedDistance)
            {
                estimatedDistance = (int)Math.Floor(Math.Pow(++step + 1, 2) / 4);
            }
            return step;
        }
    }
}

def subsum(n):
    temp = 0
    while n - 2 > 0:
        n -= 2
        temp += n
    return temp + 1
a, b = map(int, input('Enter two intergers: ').split())
diff = abs(a - b)
n = 0
while subsum(n) + n <= diff:
    n += 1
print(n)

python 3.9.1 단계 n을 상수로 두었을 때 그 단계가 커버할 수 있는 범위는 n부터 1 + n-2 + n-4 + .....입니다.

예를 들어 단계 = 5일 경우 (1, 1, 1, 1, 1)부터 (1, 2, 3, 2, 1)까지입니다. 이게 1씩 증가시킬 수 있다는거는 윗분들이 잘 설명해주셨으니까 넘어가고

맨 처음 1은 1로만 이루어진걸 셉니다. 그리고 1씩 증가시킬 수 있으므로 처음과 끝을 제외한 애들을 2로 만들어주는걸 생각하면 (1, 1, 1, 2, 1), (1, 1, 2, 2, 1), (1, 2, 2, 2, 1)으로 양 끝을 제외한 애들을 2로 만들 수 있고 이 갯수는 단계에서 2를 빼는 것과 같습니다. 마찬가지로 2가 된 애들을 양 끝을 제외하고 3으로 만들 수 있으므로, 0보다 큰 동안 n에서 2를 빼면서 더해 가면 구간의 길이를 알 수 있습니다.

그래서 그걸 그대로 적용했더니 나오긴 하는데 2^31은 1분 걸리네요...

x, y = map(eval, input().split())
gap = y-x
if gap == 0:
    print(0)
else:
    n = int(gap**0.5)
    if gap == n**2:
        print(n*2-1)
    elif gap <= n*(n+1):
        print(n*2)
    else:
        print(n*2+1)


아래는 위 코드의 설명입니다.
입력된 두 수 x와 y의 차가 9일 때를 예로 들어보자.
그럼 이동 거리는 1, 2, 3, 2, 1 만큼씩 이동하여 x에서 y로 이동할 수 있다.
그런데 차가 9에서 1씩 증가할 때 어떻게 되는지 살펴보자.
1에서 n까지의 누적합은 n*(n+1)/2 이므로 1에서 n까지의 누적합과 n-1에서 1까지의 누적합을
더하면 n*(n+1)/2 + (n-1)*n/2 = n**2이다. (누적합은 x, y의 차, 누적되는 수의 갯수는 이동 횟수)

   9 : 1 2 3 2 1        합 : 3*3 = 9
  10 : 1 2 3 2 1 1
  11 : 1 2 3 2 2 1
  12 : 1 2 3 3 2 1      합 : 3*(3+1) = 12
  13 : 1 2 3 3 2 1 1
  14 : 1 2 3 3 2 2 1
  15 : 1 2 3 3 3 2 1
  16 : 1 2 3 4 3 2 1    합 : 4*4 = 16

위의 예를 살펴보면 두 수의 차가 n의 제곱일 때 n*2-1번의 이동이 필요하며
거기에서 두 수의 차가 더 커져서 n*(n+1) 이 될 때까지는 n*2번의 이동이 필요하며
거기에서 두 수의 차가 더 커져서 (n+1)의 제곱이 될 때까지는 n*2+1번의 이동이
필요함을 알 수 있다.

// Rust

// 단계별로 다음 단계 나올 수 있는 위치들을 set에 넣어 계속 루프를 돌립니다..

// 마지막 위치에 이동거리 1로 도달하는 순간 결과를 반환합니다

fn step_1d() {

// let (start, target) = (45, 48);
// let (start, target) = (45, 49);
let (start, target) = (45, 50);

let mut step = 1;
let mut steps = HashSet::new(); // (이전 단계에서 이동 길이, 현재 위치)
steps.insert((1, start+1));     // first step

'outer: loop {
    step += 1;
    steps = next_pos(steps);
    for step in &steps {
        if step.0 == 1 && step.1 == target {
            break 'outer;
        }
    }
}
println!("{}", step);

} use std::collections::HashSet; fn next_pos(set: HashSet<(i32, i32)>) -> HashSet<(i32, i32)> {

let mut result = HashSet::new();
for (l_prev, pos) in set {    
    let mut l_next = vec![l_prev, l_prev + 1];
    if l_prev - 1 > 0 { l_next.push(l_prev-1);}
    for l in l_next { result.insert((l, pos + l));}
}
result

}