[백준/BOJ/1011] Fly me to the Alpha Centauri

1011 | Fly me to the Alpha Centauri

문제 접근 & 설계

• 우주선은 이전 작동시기에 k광년을 이동하였으면 k-1, k, k+1 안으로 이동할 수 있다.
• 처음 작동시 -1, 0, 1을 이동할 수 있으면 다음은 0, 1, 2 이동가능
• 우주선은 최소 작동 횟수로 x에서 출발하여 y로 도착해야한다.
• y지점에 도착하기 직전은 안전을 위해 1광년으로 이동해야한다.
  • 즉 y직점에 도착할 때쯤 감속해야한다.

설계

• 접근 자체가 어려웠던 문제..
• 핵심은 속도를 최대한 증가시키다가 감속해야한다는 것이다.

증가와 감속을 1, 2, 3 .. n-1, n, n+1, ..., 3, 2, 1로 표현한다면,
최소한으로 이동할 수 있는 경우는

1 : 1
4 : 1 -> 2-> 1
9 : 1 -> 2 -> 3 -> 2 -> 1
16 : 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1
...

즉 위와 같이 제곱수여야 최소한으로 이동할 수 있다.
이것을 생각하는데 3만년정도 걸렸다

9와 16사이의 수를 생각해보자

15는 1+2+3+2+1보다 6만큼이 더 필요하다.
하지만 여기서 6을 만들기 위해 1+2+3+2+1에 3보다 더 큰 수인 4를 더한다면 감속이 불가능해진다.
10부터 15까지의 수가 모두 4를 더한다면 감속이 불가능하다.

여기서 9의 base 수를 3이라고 하고, 16의 base 수를 4라고 하면
9부터 15까지의 수는 base를 넘는 수를 더해 만들 수 없다. 즉 3이하의 수로 남는 수(6)을 만들어야 한다.

또 여기서 최소한의 수로 남는 수를 만들어야하므로 탐욕법을 생각했다.
9(1+2+3+2+1)에서 15를 만들기 위해 6이 필요하고 6은 3이하의 수로만 만들 수 있다.
여기서 3이하의 수는 1, 2, 3으로 1씩 증가하는 등차수열이기 때문에 탐욕적 속성을 갖는다.
(2를 쓰는 것이 1을 두번 쓰는 것보다 무조건 좋은 방법이므로)
이런 이유로 큰 수부터 작은 수까지 남은 수에서 뺴주면서 남은 거리가 0이 되도록 문제를 해결했다.

def solution(x, y):
    total_count = 0
    base = 1 # base는 제곱수인 n을 만들 수 있는 m
    base_count = 0
    distance = y - x
    remainder = 0 # 가야하는 거리에서 제곱수를 뺀 값

    while True:
        if base * base > distance:
            base -= 1
            base_count = (base * 2) - 1
            break
        base += 1

    total_count += base_count
    remainder = distance - (base * base) # distance가 15라면 base는 3이고 remainder는 6

    while True:
        if remainder - base >= 0:
            total_count += 1
            remainder -= base
        else:
            base -= 1
        if remainder == 0:
            return total_count

사용한 스킬

시간 복잡도

• while : O(n)

total o(n)

개선

난이도

알고리즘 분류

• 수학

소스코드 📃