Fly me to the Alpha Centauri - baekjoon 1011번

Fly me to the Alpha Centauri

한번 이동하고 난 후, -1, 0, 1을 이동할 수 있는 공간 이동 장치가 있다.
x지점부터 y지점까지 이동하는데 공간이동 장치 작동을 몇번하는지 구하는 문제이다.

접근 방법

이동 거리와 작동 횟수를 표로 정리한 것이다.
이를 보면, 이동 거리 1과 2는 반복횟수가 1번씩, 3~6은 2번씩, 7~12는 3번씩 늘어나는 규칙을 찾을 수 가 있다.

빨간선은 반복횟수를 기준으로 나눈 것이다.
반복횟수의 기준이 되는 이동 거리를 구한다면 2, 6, 12 …이 될 것이다.
그러면 공식은 n * (n + 1) 될 것이다.

파란선은 빨간선에서 구간 별로 나눈 것에서 작동 횟수를 구하기 위함이다.
n**2 보다 크면 공간이동 작동 횟수 = n * 2,
n**2 보다 작거나 같으면 공간이동 작동 횟수 = n * 2 - 1 이 된다.

코드

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
	x, y = map(int, input().split())
	distance = y - x
	
	n = 0
	
	while True:
		if distance <= n*(n+1):
			break
		n += 1
	
	# 총 이동 거리가 n의 제곱보다 작거나 같을 때
	if distance <= n**2:
		print(n*2-1)
	# 총 이동 거리가 n의 제곱보다 클 때
	else:
		print(n*2)

참고

• 코드짜는 문과녀