알고리즘 - Python / 백준 - 1011번 : Fly me to the Alpha Centauri

1011번: Fly me to the Alpha Centauri (acmicpc.net)

1011번: Fly me to the Alpha Centauri

 

---

풀이

• 어느 구간을 우주선이 이동한다고 가정할 때 , 움직일 수 있는 거리는 이전 움직인 거리에 +1 , +0 , -1 한 경우이다.
• 출발과 도착 구간을 1만큼 움직이며 , 가장 적게 움직이는 횟수를 구하는 문제다.
• 어느 구간을 최소 횟수로 도달하는 가장 직관적인 방법은 1 , 2 , 3... k , k-1 , k-2... 2 , 1 일 것이다.
• 위 경우의 움직인 거리를 모두 더하면 k^2 이다.
• 위를 통해서 알 수 있는 점은 어떠한 수를 기준으로 좌, 우가 정확히 대칭이 될 때 , 최소로 움직이는 경우라는 것이다.
• 따라서 이를 알아보기 위해 좌우가 대칭이 되는 경우를 모두 나열해 보았다.

 

 

 

• 위의 그림에서 알 수 있듯이 대칭 구조를 가질 때 , 해당 거리를 최소한의 횟수로 움직인다.
• 대칭 구조가 아닌 거리는 그 보다 큰 대칭구조에서 중간의 수를 알맞게 빼어 만들 수 있으므로 그 횟수를 따라간다.
• 즉 예를 들어 10의 경우 그보다 큰 대칭구조인 12 ( 1 2 3 3 2 1 )에서 중간에 3 2을 2 1로 바꾸면 된다.
• 이는 , 아래의 그림을 통해 살펴보면 더욱 쉽게 이해 가능하다.

 

 

 

 

 

n = int(input())
for _ in range(n):
    a,b = map(int , input().split(" "))
    ans ,way = 2 , b-a
    check , weight= 2 , 2
    if way == 1:
        print(1)
    elif way == 2:
        print(2)
    else:
        p = False
        while True:
            for _ in range(2):
                weight += check
                ans += 1
                if way <= weight:
                    p = True
                    break
            check += 1
            if p == True:
                break
        print(ans)

---