[파이썬/python] 백준 - 1011 Fly me to the Alpha Centauri

문제

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

---

문제 설명

1. 공간이동 장치를 통해 x지점에서 y지점으로 이동을 하려고 한다.
2. 공간이동 장치는 이동 조건이 있다.
   1. 이동 거리는 0부터 시작해서 이전 이동거리가 k라면 다음 이동은 k-1, k, k+1만 이동이 가능하다.
   2. y지점에 도착하기 전 마지막 지점에서는 1의 거리로 이동해야 한다.
3. x지점에서 y지점으로 정확히 이동하는데 필요한 장치의 최소 작동 횟수를 구해라.

 

---

풀이

처음에는 그래프 탐색 혹은 DP로 접근하는 문제인가?라고 생각했다. 결국에는 앞으로만 전진하기 때문이다. 하지만 x와 y의 범위가 $2^{31} = 10^9$정도이기 때문에 말도 안 된다고 생각하고 다른 방법은 고안했다.

 

일단 시작지점과 마지막 지점은 1이라는 힌트가 주어졌기 때문에 양방향에서 동시에 늘려가면서 계산하면 정답이 나올 것 같았다.

 

예를 들면 이런 식이다.

 

 1 2 3 2 1

1 2 3 4 5 4 3 2 1...

이런 식으로 i만큼 거리를 늘려가며 i*2씩 장치가 이동해야 무조건 y로 도착이 가능하다.

 

여기까지의 문제였으면 굉장히 쉽게 풀 수 있었을 텐데 한 가지 문제가 존재했다.

 

다음 이동할 거리 즉 (i+1)*2 보다 작은 거리가 존재할 때.. 는 어떻게 해야 하지 라는 고민이다.

1 2 3 4 5 4 3 2 1 일 때 다음으로 계산할 거리를 예상해 보면 6 + 6 = 12가 될 것이다.

 

근데 만약 1 2 3 4 5 (남은 거리 = 10) 5 4 3 2 1이라면?

그렇다면 양쪽에서 늘리기만 해서는 정답을 찾을 수 없다.

 

그런데 생각해 보자. 남은 거리가 다음 (i+1)*2보다 작다면 사이클을 새로 만들지 않고 i보다 작은 숫자를 넣어서 완성해도 되지 않을까? 예를 들면 1 2 3 4 5 (5 5) 5 4 3 2 1처럼 말이다. 왜냐하면 숫자는 k-1, k, k+1 모두 들어갈 수 있기 때문이다.

 

그런데 이게 최소라는 보장이 있을까?라는 의문을 해소해야 한다.

 

핵심은 남은 거리가  (i+1)*2보다 작다는 것에 존재한다. 결국에는 다음 6*2를 넣을 수 없기 때문에 나머지 거리는 6보다 작은 숫자들로만 구성을 해야 한다.

 

이해를 돕기 위해 모든 경우의 수를 검증해 보자.

남은 거리: 12 => 1 2 3 4 5 (6 6) 5 4 3 2 1

남은 거리: 11 => 1 2 3 4 5 (6 5) 5 4 3 2 1

남은 거리: 10 => 1 2 3 4 5 (5 5) 5 4 3 2 1

남은 거리:   9 => 1 2 3 4 5 (5 4) 5 4 3 2 1

남은 거리:   8 => 1 2 3 4 5 (4 4) 5 4 3 2 1

남은 거리:   7 => 1 2 3 4 5 (?) 5 4 3 2 1

남은 거리:   6 => 1 2 3 4 5 (?) 5 4 3 2 1

남은 거리:   5 => 1 2 3 4 5 (?) 5 4 3 2 1

남은 거리:   4 => 1 2 3 4 5 (?) 5 4 3 2 1

남은 거리:   3 => 1 2 3 4 5 (?) 5 4 3 2 1

남은 거리:   2 => 1 2 3 4 5 (?) 5 4 3 2 1

남은 거리:   1 => 1 2 3 4 5 (?) 5 4 3 2 1

 

기존에 검증하기로 한 방식으로 만들 수 있는 경우는 12, 11, 10, 9, 8 정도이다. 그보다 작은 숫자들은 어떻게 넣어야 할까?

 

먼저 12부터 8까지는 현재 넣을 수 있는 가장 큰 숫자인 6, 5, 4로 모두 최소로 만들 수 있다는 것을 검증했다.

7부터는 다른 방식을 고민해야 한다.

 

먼저 기존에 넣기로 한 6 혹은 5를 넣게 되면 1 or 2가 남게 된다. 따라서 이 숫자를 넣지 못한다.. 그럼 남은 숫자를 대체 어디에 넣어야 할까? 그냥 기존에 만든 위치에 넣으면 된다. 1 2 2 3 4 5 5 5 4 3 2 1 이런 식으로 말이다.

 

그렇다면 그 아래의 6부터 1까지는 같은 방식이다. i+1인 6보다 작은 숫자는 그냥 나왔던 위치에 중복으로 끼워 넣으면 된다는 말이다.

남은 거리:   6 => 1 2 3 4 5 6 5 4 3 2 1

남은 거리:   5 => 1 2 3 4 5 5 5 4 3 2 1

남은 거리:   4 => 1 2 3 4 4 5  5 4 3 2 1

남은 거리:   3 => 1 2 3 3 4 5 5 4 3 2 1

남은 거리:   2 => 1 2 2 3 4 5 5 4 3 2 1

남은 거리:   1 => 1 1 2 3 4 5 5 4 3 2 1

 

따라서 두 가지의 조건을 통해 결과를 도출할 수 있다.

1. 남은 거리 - i <= 0이라면 현재 i보다 작은 수 1개만 넣어도 사이클을 만들 수 있으니 기존 cnt + 1을 반환한다.
2. 남은 거리 <= 0이라면 이미 i*2만큼을 할 수 없다는 의미이고, 1개만 넣어서 사이클을 만들 수 없기 때문에 기존 cnt에 2를 더한 값을 반환한다.

 

내 코드에서는 먼저 남은 거리를 구하면서 cnt을 변환했기 때문에  2번 조건을 검사할 때 이미 cnt는 선반영 되어있는 상태이다.

따라서 현재의 cnt를 반환해서 결과를 도출했다.

 

이 문제는 따로 알고리즘을 요구하진 않았고, 수학적인 사고력을 가지고 풀어야 하는 문제라고 느꼈다.

---

코드

import sys
input = sys.stdin.readline

for t in range(int(input())):
    x,y = map(int,input().split())

    dist = y-x
    i = 1
    cnt = 0
    while True:
        if dist <= 0:
            break
        elif dist-i <= 0:
            cnt += 1
            break
        
        dist -= 2*i
        i += 1
        cnt += 2
    print(cnt)

---

시간복잡도

• 이 코드는 $N$이 $2*i$만큼 줄어든다
• 결국에는 2*(1+2+3+4+5... i)까지 반복할 것이고 이 숫자는 결국 dist에 수렴할 것이다.
• 따라서 시그마 공식을 통해 $dist = 2*(1+2+3... i) = i(i+1)$이다.
• 시간복잡도는 가장 큰 차수만 고려하기 때문에 $dist = i^2$ 정도라고 고려하겠다.
• $O(\sqrt {dist})$, 최악의 경우 $dist = 2^{31} = 10^9$ 이므로 약 $O(10^5)$정도라고 생각하면 되겠다.