1011.Fly me to the Alpha Centauri

https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

문제는 보고 오도록

골드지만 생각보다 간단한 문제다

이 문제의 핵심은 우주선이 n 광년 움직였다면 다음에는 n-1 , n, n+1 광년 움직일 수 있다는 점
그리고 어차피 거리가 중요하기 때문에 시작점과 끝점은 중요하지 않다

결과적으로 최소로 움직이려면은 크게 움직여야 하기 때문에 n 광년, n+1광년, n+2 광년 이런 식으로 움직여야 한다
근데 이거 어디서 많이 보던 패턴이다 n +n+1 + n+2 + n+3 고등학교 수학 책에 나오는 등비수열
공차가 1인 수열의 합 공식은

이고 주어진 거리보다 작은 최대 정수를 구하면 풀린다 

하지만 문제의 조건에서 마지막은 1광년움직인다 했으니까 

 

등비수열이 1로시작해 n 까지 갔다가 다시 1로 끝나는 형식로 만들어져야한다 

그러면 중심으로 대칭이기 때문에 

주어진 거리를 2로 나눈값보다 작은 최대 정수를 구해야한다 

여기서 N은 2차함수니까 근의 공식을 사용해  N값을 구하고 소수점은 버린다 

n을 구했다면 거의 끝났다 

 

2개의 수열이 만나는 부분에서 문제가 생기는데 만약 거리가 7 일때는  1,2,3,3,2,1 처럼 정확한 대칭이라 상관없지만 8일때는 1,2,3,3,2,1 에서 1이 남아 대칭이 아니다 

 

이 문제를 해결하기 위해서는 거리 X 에서 두 수열의 합을 뺀 값이 얼마인지 확인하고 처리해줘야 한다

만약 이 값이 0이라면 정확한 대칭이라 상관없다
elif n 보다 작거나 같다면 n까지 가는 도중에 한번 차이만큼 더해주면 해결된다
elif n 보다 크다면은 최대인 n 한 번으로 못하니까 2번은 더해줘야 한다
차이가 2n 보다 큰 경우는 없다 만약 그랬다면 애초에 근의 공식을 사용했을 때 n 값이 증가했을 테니까.

for i in range(int(input())):
    a,b=map(int,input().split()) # 입력
    x=b-a     # 거리 
    n=int((-1+(1+4*x)**0.5)//2)  # 근의 공식사용 N 값구하기 
    ans=x-(n*n+n)   # 마지막 처리
    print(2*n +(0 if ans==0 else (1 if ans<=n+1 else 2)) )

이제 우현이는 옥수수밭을 떠날 수 있게 되었다