알고리즘 문제풀이: Fly me to the Alpha Centauri

NameError·2021년 4월 14일

문제 링크

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

풀이 전 계획과 생각

이 문제의 내용을 요약하면
n번째 이동량이 i라면
n+1번째 이동량은 i-1, i, i+1 중에서 0보다 큰 값만 가능하다. (0도 가능하지만 0이 여러 번 반복되면 최소 이동 횟수가 아니게 되니까 빼면 된다.)

그리고 첫번째 이동과 마지막 이동은 반드시 1이다.

이 문제를 보면서 별의별 생각을 다 해 보았다.

첫 이동량이 1이니까 다음은 1,2 중 하나고,
그 다음은 1,2,3 중 하나고,
그 다음은 1,2,3,4 중 하나고... 이걸 모두 더해서 주어진 거리가 나올 때까지 무한 반복해야 하나? 게다가 마지막이 1인 경우만 한해서? ㅋㅋㅋ

그러다가 문득 유레카! 하고 생각이 떠올랐는데

그것은 처음과 마지막은 반드시 1이고 이동량 변화는 1 이하만 가능하니까 이동 횟수를 최소화하고 한 번에 최대한 많이 이동하려면...

예를 들어 입력값 n=9인 경우 최선의 이동량은 1+2+3+2+1이고 횟수는 5일 수밖에 없다.
3+3+3 이런 건 불가능하고, 첫 값이 1, 마지막 값이 1인 한도 내에서 1씩 증가, 감소만 가능하기 때문이다.

1+2+3+2+1의 합은 무엇일까?
최댓값 3을 x라고 했을 때 1부터 x까지의 합 + 1부터 x-1까지의 합이니까
즉 x(x+1)/2+x(x-1)/2 = x(2x)/2=x^2 이고
이 경우의 이동 횟수는 x+x-1=2x-1이다.

다음으로 전형적인 이동 경로는
n=12일 때 1+2+3+3+2+1 이런 식으로 되는 경우이다.
이 경우 x=3이라고 하면
n = x(x+1)/2+x(x+1)/2 = x(x+1)이고
이 경우의 이동 횟수는 2x이다.

이와 같이 이동 횟수는 점진적으로 늘어나며 n=x^2 또는 n=x(x+1)인 x를 기준으로 판정할 수 있다.

n=1 → 1 n=x^2인 경우로 최소 이동 횟수는 2x-1
n=2 → 1,1 → 2 n=x(x+1)인 경우로 최소 이동 횟수는 2x
n=3 → (1+2+1은 4니까 안 되고) 1,1,1 → 3
n=4 → 1,2,1 → 3 n=x^2인 경우로 최소 이동 횟수 2x-1
n=5 → 1,2,1,1 → 4
n=6 → 1,2,2,1 → 4 n=x(x+1)인 경우로 최소 이동 횟수 2x
n=7 → 1,2,2,1,1 → 5
n=8 → 1,2,2,2,1 → 5
n=9 → 1,2,3,2,1 → 5 n=x^2

그렇다면 하나의 n에 대한 이동 경로는 일일이 계산할 수 없어도 이동 횟수는 다음 범위 안에 있을 것이다.

정확히 n=x^2인 경우의 이동 횟수는 2x-1
- x^2 < n < x(x+1)인 경우는 2x
정확히 x=x(x+1)인 경우의 이동 횟수는 2x
- x(x+1)<n<(x+1)^2인 경우의 이동 횟수는 2x+1
정확히 n=(x+1)^2인 경우의 이동 횟수는 2(x+1)-1 = 2x+1

풀이

# 처음과 마지막은 반드시 1이기 때문에 한 번에 가장 많이 이동하는 경우는:
# 1: 1
# 2: 1+1
# 3: 1+1+1
# 4: 1+2+1
# 5: 1+2+1+1
# 6: 1+2+2+1    
# 7: 1+2+2+1+1
# 8: 1+2+2+2+1 
# 9: 1+2+3+2+1
# 1+2+3+3+2+1
# 1부터 x까지의 합은 x(x+1)/2, 1부터 x-1까지의 합은 x(x-1)/2
# 여기에서 가능한 최소 이동경로 조합은
# x(x+1)/2 + x(x-1)/2 = x(x+1+x-1)/2 = x*2x/2 = x^2 = n인 경우에 
# 이 경우에 이동 횟수는 x+x-1 = 2x-1

# x^2=n인 x가 있는 경우 
# 즉 n=1일 때 이동 횟수는 1
# n=4일 때 이동 횟수는 3
# n=9일 때 이동 횟수는 5

# 이동 횟수가 짝수인 경우
# x(x+1+x+1)/2  = x(2(x+1))/2 = x(x+1)=n인 경우에
# 이동 횟수는 2x

# n=2일 때 이동 횟수 2
# n=6일 때 이동 횟수 4
# n=12일 때 이동 횟수 6

# 따라서 최소 이동 횟수는
# x^2=n인 x가 있는 경우에는 이동 횟수 2x-1
# x(x+1)=n인 x가 있는 경우에는 이동 횟수 2x

# 하나의 x에 대하여
# n=x^2에 대해서는 이동 횟수 2x-1
# n>x^2 and n<x(x+1)에 대해서는 이동 횟수 2x

# n을 기준으로
# root n의 바닥값이 x
# x^2=n이라면 이동 횟수 2x-1
# x^2<n<=x(x+1)이라면 이동 횟수 2x
# x(x+1)< n < (x+1)(x+1) 이라면 2(x+1)-1 = 2x+1
import math
def route(n):
    x = math.floor(math.sqrt(n))
    if x*x >=n:
        return 2*x-1
    elif x*(x+1)==n:
        return 2*x
    elif n<x*(x+1):
        return 2*x
    else:
        return 2*x+1
counter=int(input(""))
table=[]
while counter>0:
    n1,n2=input("").split()
    n3 = int(n2)-int(n1)
    #print(n3)
    table.append(route(n3))
    counter-=1
#print(table)
for item in table:
    print(item)