BAEKJOON PYTHON 1011 Fly me to the Alpha Centauri

Prob

---

Approach

 

Distance	num_move	iter
1	1	1
2	2	1
3	3	2
4	3
5	4	2
6	4
7	5	3
8	5
9	5
10	6	3
11	6
12	6

iter가 (1, 1), (2, 2), (3, 3) 씩 규칙적으로 증가하는 것을 확인 할 수 있다.

2, 4, 6, --- 의 계차가 등차인 수열로 볼 수 있으며 이는 n^2 + n으로 표시할 수 있다.

따라서 n^2 + n < distance 를 만족하는 n의 최댓값을 구하면 몇 번째 그룹에 해당하는지 구할 수 있다.

그 그룹의 중앙값 (n^2) 보다 클 경우 2n 번 이동하해야 하고, 작거나 같을 경우 2n - 1 번 이동해야 한다.

---

Code

def count_move(dis):
    n = 1
    while pow(n, 2) + n < dis:
        n += 1
    if (dis <= pow(n, 2)):
        return (2 * n - 1)
    else:
        return (2 * n)
    
if __name__ == "__main__" :
    T = int(input())
    m_move = 0 # move 수
    for i in range(T):
        x, y = map(int, input().split())
        distance = y - x
        m_move = count_move(distance)
        print(m_move)

 

출처

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