[백준][python][1011] Fly me to the Alpha Centauri

<문제>

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

1011번: Fly me to the Alpha Centauri

<어떻게 풀까?>

규칙을 찾기 위해서 일단 거리에 따른 최단 거리를 적어보자.

 

거리	최단 거리로 가는 방법
1	1
2	1, 1
3	1, 1, 1
4	1, 2, 1
5	1, 2, 1, 1
6	1, 2, 2, 1
7	1, 2, 2, 1, 1
8	1, 2, 2, 2, 1
9	1, 2, 3, 2, 1

 

이런식으로 구성이 된다. 이것만 봐도 간단한 규칙을 찾을 수 있다. 아직 못 찾으신 분들은 한 번 생각해보시길 바란다. 

이 방법들을 규칙을 보기 쉽게 재구성 해 보게 된다면 

 

거리	최단 거리로 가는 방법
1	1
2	1, 1
4	1, 2, 1
6	1, 2, 2, 1
9	1, 2, 3, 2, 1
12	1, 2, 3, 3, 2, 1
16	1, 2, 3, 4, 3, 2, 1
20	1, 2, 3, 4, 4, 3, 2, 1

 

이런 식으로 경계가 되는 값들은 대칭을 이루고 있다.

또한 증가하는 값이 2줄씩 일정하다.

즉 이 경계들을 이용해서 코드를 작성해 주면 된다.

<코드>

n = int(input())

for k in range(n):
    A, B = map(int, input().split())
    distance = B-A

    start = 1
    way = 1

    for i in range(distance):
        if start <= distance <= start+ i:
            print(way)
            break
        elif start+i +1 <= distance <= start+ 2*i+1 :
            print(way+1)
            break
        start += 2*(i+1)
        way += 2

<코드 설명>

증가하는 범위가 2줄씩 같아서 if 문과 elif문을 사용해서 코드를 작성해 주었다. 

start에서 경계가 시작된다. 그 경계를 기준으로 같은 값을 더해준다.

처음에 i를 이용해서 way를 대신하려고 했지만, 거리가 1일 때 값을 처리하기 힘들어서

그냥 way라는 변수를 만들어서 값을 출력해 주었다.

매번 말하지만 이것이 효율적인 코드라고 생각하지 않는다.

더 좋은 코드나 조언이 있다면 답들을 달아주면 좋겠다.

또한 이것을 개량해서 더 좋은 코드를 만들어 봐도 좋을 것이다.