문제가 길어서 바로 흥미가 떨어질 수 있지만 생각보다 문제는 간단하다. x지점에서 y지점으로 이동하려면 y - x만큼의 거리를 이동해야하므로 입력 값의 크기는 중요하지 않고 두 값의 차이만 구해서 이용해주면 된다. 테스트 횟수 T를 입력받기때문에 T번만큼 반복문을 사용하면 될 것이다.
k만큼 이동했으면 다음 이동 거리는 k-1, k, k+1중 하나만큼 이동할 수 있고, 어떻게 하면 최대한 적은 횟수만큼 이동하여 도착할 수 있는 지가 문제의 핵심이다.
거리가 크게 떨어져 있다고 생각해 보면 가능한 한 빨리 큰 숫자만큼 이동하게 만들어줘야하므로 초반에는 계속 k+1만큼 이동을 할 것이고, 너무 멀리까지 k+1을 하다보면 도착지점 바로 전에 1만큼 이동하지 못할 것이다. 그러므로 최대한 중간에서 k+1을 멈추고 k-1로 줄이면서 도착지점까지 가면 된다. 규칙을 한번 찾아보면, (출발과 도착전 1이동은 1'로 표시했다.)
1: 1' 1
2: 1' + 1' 2
3: 1' + 1 + 1' 3
4: 1' + 2 + 1' 3
5: 1' + 2 + 1 + 1' 4
6: 1' + 2 + 2 + 1' 4
7: 1' + 2 + 2 + 1 + 1' 5
8: 1'+ 2 + 2 + 2 + 1' 5
9: 1' + 2 + 3 + 2 + 1' 5
10: ...... 6
11: ..... 6
12: ..... 6
............
이런 식으로 각 거리에 따라 결과 값이 (1) (2) (3,4) (5,6) (7,8,9) ... 의 숫자 쌍이 1부터 1씩 증가하면서 반복되는 것을 알 수 있다. 거리가 각각 1, 2, 4, 6, 9... 을 넘어가는 순간 cnt 값을 하나씩 증가시켜 주면 된다.
그러려면 +1 , +1 , +2, +2, +3, +3 .. 식으로 증가하는 move 변수를 하나 설정해야 된다.
또한 move는 2번이 지날 때 마다 1씩 증가하기 때문에 cnt가 2의 배수일 때 1씩 증가하도록 만들어 준다.
move_plus 변수는 move를 더해줘서 반복문이 돌 때마다 1,2,4,6,9...로 값이 변하게 해준다. 이 move_plus변수보다 distance(거리) 가 작으면 계속 진행을 시켜주고 그렇지 않으면 반복문을 나가서 cnt 값을 출력해주면 된다.
if __name__ == "__main__" :
T = int(input())
for i in range(0, T): #T번의 테스트 케이스
X, Y = map(int, input().split())
distance = Y - X
cnt = 0
move = 1 #+1, +1, +2, +2, +3, +3, ...
move_plus = 0
while move_plus < distance:
cnt += 1
move_plus += move #cnt에 해당하는 move만큼 이동거리의 합에 더해준다.
if cnt % 2 == 0 : #2,2 3,3 4,4 5,5 ... 식으로 cnt의 빈도가 늘어나기 때문에
move += 1 #2번에 한번씩 move를 1씩 증가시켜준다.
print(cnt)이 문제를 푸는 데 꽤 오랜 시간이 걸렸다. 백준 문제들은 테스트 케이스의 입력값이 엄청 큰 경우가 많기 때문에, 처음에 짠 코드는 값은 잘 나오지만 시간초과가 떠서 코드를 버려야 했다. 아마 반복문을 두개 이상 돌기 때문인 것 같다.
반복을 최대한 줄이기 위해서는 거리를 1씩 증가시키면서 cnt값의 변화를 세는 것이 아니라, cnt 값의 변화에 따른 이동거리의 최대값을 이용하는 것이 문제의 해결법이었다.
