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

문제 링크

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)

풀이하면서 막혔던 점과 고민, 소감

우선 문제가 무척 어려웠는데 한 번에 맞혀서 매우 기뻤다.

문제 자체는 일단 수열의 구조를 이해하기 시작하니까 술술 풀렸는데 정말 어려웠던 부분(!)은 입력값의 형식이었다.

입력의 첫 줄에는 테스트케이스의 개수 T가 주어진다. 각각의 테스트 케이스에 대해 현재 위치 x 와 목표 위치 y 가 정수로 주어지며, x는 항상 y보다 작은 값을 갖는다. (0 ≤ x < y < 231)

첫째줄에는 값을 몇 쌍 입력할지 입력하고 둘째줄부터 처음에 입력한 수만큼 출발점과 도착점의 좌표를 입력해야 하는데...

많은 시행착오 끝에 구글링을 해서 반복문에 두 개의 값을 입력받는 input을 이렇게 입력했다.

n1,n2=input("").split()

아무튼 한 번에 맞혀서 너무 기쁘고... 이제 다음 문제를 풀어보겠다.