1주차_과제_2_Fly me to the Alpha Centauri

1. 문제 링크
   링크텍스트

2. 풀이 전 계획 및 생각
   늘이기와 줄이기는 1씩만 가능하고 마지막이 1로 끝나야 하므로 현재 거리를 기준으로 다음 이동하는 광년이 +1일지 +0일지 -1일지를 구하는 공식을 생성한다.
   남은 거리가 (현재값+1) + (현재값) + (현재값-1) + .. + 1 과 같거나 크면 이동 하는 광년을 +1 하고 그보다는 작으나 (현재값) + (현재값-1) + .. + 1 과 같거나 크면 현재 이동 광년 유지, 그 외의 경우 -1을 하면서 이동하면 총 몇번을 해야 하는지 나온다.

3. 풀이

def fly(start, end):
	distance = end -start
	current_jump_dist = 1
	jump_count = 1
	distance = distance - current_jump_dist
	while distance != 0:
		if current_jump_dist % 2 == 1:
			factory_sum = (current_jump_dist +1 ) * (current_jump_dist // 2) + (current_jump_dist + 1) / 2
		else:
			factory_sum = (current_jump_dist + 1) * (current_jump_dist // 2)
		upper_current = current_jump_dist + 1
		lower_current = current_jump_dist - 1
		if distance >= factory_sum + upper_current:
			current_jump_dist = upper_current
		elif distance >= factory_sum :
			current_jump_dist = current_jump_dist
		else:
			current_jump_dist = lower_current
		distance = distance - current_jump_dist
		jump_count += 1
	return jump_count 	
output_array=[]
num_loop=int(input())
for num in range(num_loop):
	start,end=map(int,input().split())
	output_array.append(fly(start,end))
	for num in range(num_loop):
	print(output_array[num])

4. 풀이하면서 막혔던 점과 고민했던 점
   factory_sum 계산식에서 괄호를 안 해서 결과가 달리나온점. python version에 따라 input.split()가 정상적으로 먹히지 않았던 문제. +1,0,-1을 판단하는 조건문에서 = 의 유무에 따라 달라지는 결과.

5. 풀이 후 알게된 개념과 소감
   1씩 줄여가며 sum 하는 식을 한줄로 줄이는 것이 code적으로 좋은 건지 for 문으로 돌리는게 code 적으로 좋은 것인지 고민함. 보기에는 for문이 좋지만 결과적으로는 시간복잡도가 O(n)인데 반해 계산식을 마련하면 O(1)로 더 간단함.