설명

프로그래머스의 점프와 순간 이동 문제다. 일정 거리를 이동해야 하는 상황에서 배터리를 한 칸 소모해서 앞으로 이동하거나 비용 없이 현재까지 진행한 거리의 2배 위치로 텔레포트할 수 있는 슈트가 있다고 할 때 주어진 거리까지 이동할 수 있는 최소한의 배터리 비용을 계산하는 문제다.

비용이 들지 않는 텔레포트가 무슨 말이냐면 이 슈트를 입고 이동한 거리가 3일 때 6까지 아무런 비용 없이 이동할 수 있다는 것이다. 그럼 굳이 배터리를 소모하면서 한 칸씩 이동할 필요 없이 텔레포트만 하면 되는게 아닐까?

하지만 시작 위치에서는 이동한 거리가 0이기 때문에 아무리 텔레포트해도 0 * 2 = 0으로 영원히 움직일 수 없다. 그러므로 최소한 한 번은 움직여야 하며 두 배씩 이동하는 텔레포트 특성상 2의 제곱수에만 도달할 수 있을 것이다.

문제에서는 해당 위치에 정확하게 이동하는 것을 요구하고 있다. 만약 5의 거리를 이동해야 한다면 배터리를 5만큼 소모하여 1 5 = 5만큼 이동할 수 있고 1칸만 이동한 후 두 번 텔레포트, 즉 1 2 * 2 = 4로 이동한 후 다시 1칸 이동해서 배터리를 2만큼 소모하고 5만큼 이동할 수 있다. 어쨌든 목적지를 넘어가면 안됀다는 것이다.

풀이

재귀 DFS 탐색(재귀 한도 초과)

처음에 시도했던 방법은 DFS로 그래프를 그려가면서 탐색하는 방법이었다. 일단 처음에 한 칸 이동하고 그 다음부터는 재귀로 배터리를 소모해서 한 칸 더 이동하는 경우와 배터리를 소모하지 않고 현재 위치에서 텔레포트하는 경우를 분기로 설정해서 재귀적으로 호출하는 방식이었다.

문제의 조건 자체는 복잡하기 않았기 때문에 그리 어렵지 않게 구현할 수 있었는데 간과한 점은 문제에서 주어질 수 있는 목적지의 거리가 100000000, 즉 1억까지 주어질 수 있다는 것이다.

실제로 위처럼 코드를 작성한 결과 테스트 케이스(5000)도 통과하지 못해서 코드를 다시 작성해야 했다.

minimum_battery_use = None

# 재귀 호출되는 DFS 함수
def move(battery_use, current_position, destination):
    global minimum_battery_use
    # 현재 이동거리가 목적지와 동일한 경우 배터리 최소 소모값 갱신
    if current_position == destination:
        minimum_battery_use = min(minimum_battery_use, battery_use)
    # 아직 목적지에 도착하지 않은 경우 계속 이동
    elif current_position < destination:
        # 배터리를 소모하고 한 칸 앞으로 이동
        move(battery_use+1, current_position+1, destination)
        # 배터리를 소모하지 않고 현재 위치의 두 배 위치로 텔레포트
        move(battery_use, current_position * 2, destination)
    

def solution(n):
    global minimum_battery_use
    minimum_battery_use = n
    # 일단 한 칸은 이동하고 시작해야 한다.
    move(1, 1, n)

    return minimum_battery_use

큐 BFS 탐색(시간 초과)

두번째로 시도한 방법은 큐를 이용한 BFS 탐색이다. 큐는 삭제 연산이 빈번하기 때문에 O(1)의 속도를 가지는 collections 모듈의 deque 클래스를 활용했다.

하지만 단순히 DFS에서 BFS로 바꾼것만으로는 여전히 5000의 테스트 케이스를 통과하지 못했다. 그래서 고민하다가 최적화 방법이 하나 더 생각났는데 만약 현재 배터리 소모량이 다른 노드에서 측정된 최소 배터리 소모량보다 크다면 더이상 탐색하지 않고 중단하는 것이다. 이걸 백트래킹이라고 하는지 잘 기억이 안나지만 아무튼 테스트 케이스를 통과하고 정확도 테스트도 모두 통과할 수 있었다.

from collections import deque


def solution(n):
    minimum_battery_usage = n
    queue = deque() # BFS 탐색을 위한 큐(데크)
    queue.append((1, 1)) # 현재 배터리 사용량, 현재 위치 튜플
    
    while queue:
        current_battery_usage, current_position = queue.popleft()
        # 현재 배터리 사용량이 최소 배터리 사용량을 초과하는 경우 무시
        if current_battery_usage > minimum_battery_usage:
            continue
        
        # 목적지에 도달한 경우 최소 배터리 사용량 갱신
        if current_position == n:
            minimum_battery_usage = min(minimum_battery_usage, current_battery_usage)
        elif current_position < n:
            # 목적지에 도달하지 못한 경우 이동, 텔레포트 BFS
            queue.append((current_battery_usage+1, current_position+1))
            queue.append((current_battery_usage, current_position * 2))

    return minimum_battery_usage

하지만 효율성 테스트는 전부 통과하지 못했는데 아무래도 1억까지 주어질 수 있는 문제의 특성상 그래프 탐색으로는 한계가 있는 듯 했다. 어떻게 풀어야 할까?

산술 연산

이 풀이는 이곳에서 영감을 받을 수 있었다.

문제에서 제일 중요한 특징은 현재 위치의 두 배의 위치로 이동하는 텔레포트가 아무런 배터리도 소모하지 않는다는 것이다. 그렇다면 모든 목적지를 최대한 텔레포트를 이용하여 이동할 수 있다면 최소 배터리 소모량을 얻을 수 있지 않을까?

하지만 모든 목적지는 2의 제곱수가 아니기 때문에 목적지부터 역순으로 탐색하면서 최대한 2의 제곱수로 이동할 수 있도록 계산하는 과정이 필요했다. 그래서 생각한 방법은 목적지의 거리를 2로 나눠가면서 나누어 떨어지지 않는 즉 2의 제곱수가 아닌 경우 배터리를 소모해서 이동하고 그 외의 경우에는 텔레포트를 사용해서 배터리를 소모하지 않는 방법이었다.

1부터 2를 곱하며 시작하기보다는 목적지부터 2로 나누면서 필요한 경우에만 한 칸씩 이동하는게 더 최적화된 방법일 것이다. 테스트 케이스로 주어진 5000을 예로 들어보자.

• 5000
• 2500
• 1250
• 625
• 312.5
  • 2로 나누어 떨어지지 않으므로 텔레포트만으로 이동할 수 없다.
  • 312에서 텔레포트해서 624로 이동 후 한 번 움직여야 한다.
• 312
• 156
• 78
• 39
• 19.5
  • 2로 나누어 떨어지지 않으므로 텔레포트 만으로 이동할 수 없다.
  • 19에서 텔레포트해서 38로 이동 후 한 번 움직여야 한다.
• 19
• 9.5
  • 2로 나누어 떨어지지 않으므로 텔레포트 만으로 이동할 수 없다.
  • 9에서 텔레포트해서 18로 이동 후 한 번 움직여야 한다.
• 9
• 4.5
  • 2로 나누어 떨어지지 않으므로 텔레포트 만으로 이동할 수 없다.
  • 4에서 텔레포트해서 8로 이동 후 한 번 움직여야 한다.
• 4
• 2
• 1
• OK!
  이처럼 총 4번을 직접 이동해야 하며 맨 처음 이동하는 횟수까지 합치면 5번의 이동, 즉 5만큼 배터리를 소모하여 5000이라는 거리를 이동할 수 있다.

이를 기반으로 작성한 코드는 다음과 같다.

def solution(n):
    ans = 1

    while n > 1:
        n = n / 2
        if round(n) != n:
            ans += 1
            n = int(n)

    return ans

후기

처음에는 DFS나 BFS같은 탐색 문제인 줄 알았는데 오히려 수학쪽에 더 가까운 문제였다. 프로그래머스 서머 코딩의 다른 문제도 수학쪽 문제가 나왔던 것 같은데 서머 코딩의 특징일지도 모른다.

텔레포트를 사용하면 비용 없이 이동할 수 있고 2배씩 이동할 수 있다는 점에 집중했어야 하는 것 같다.