C언어 221제] 단계(Steps)

출처 : 반크_반크 20년 백서

 

문제]

수직선 위에서 정수 x에서 정수 y로 이동하는 과정을 생각해보자. 각 단계의 길이는 음이 아니어야 하며 이전 단계의 길이보다 1이 작거나 같거나 1이 커야 한다.

x에서 y로 가는 데 필요한 최소 단계의 수는 얼마인가? 첫번째와 마지막 단계의 길이는 모두 1이어야 한다.

입력
첫번째 줄에는 테스트 케이스의 개수인 n이 입력된다. 한 줄에 하나씩의 테스트 케이스가 입력되면 각 줄마다 두 개의 정수 x, y가 입력된다. 0<=x<=y<2^31이다.

출력
각 테스트 케이스에 대해 x에서 y로 이동할 수 있는 최소 단계 수를 한 줄에 하나씩 출력한다.

입력 예
3
45 48
45 49
45 50

출력 예
3
3
4


출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어) : 문제 48 단계(Steps) p181

 

참고 풀이]

#include <stdio.h>

int main()
{
   int i, j, t, x, y;
   int Sum;
   int Result;

   scanf("%d",&t);
   for(i=0; i<t; i++)
   {
      scanf("%d%d",&x, &y);

      if(x>=0 && x<=y && (long long)y<(long long)pow(2,31))
      {
         if(y-x==0) Result=0;
         else if(y-x==1) Result=1;
         else
         {
            Sum=1;
            for(j=2;Sum<y-x;j++)
               Sum+=(j+1)/2;
            Result=j-1;
         }
         printf("%d\n",Result);

      }
   }
   return 0;
}

 

참고 풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 가을