문제

문제링크

정방향 알고리즘 : 1에서 n까지 이동

from collections import deque

batteries: set = set()
flag: set = set() # dp와 같은 효과


class Node:
    def __init__(self, distance, battery):
        self.distance = distance
        self.battery = battery
        

def bfs(n):
    global batteries
    q = deque()
    q.append(Node(1,1))
    
    while q:
        now = q.popleft()
        # 이 부분에서 early continue를 하여서 연산량 감소 시킴
        if now.distance in flag:
            batteries.add(now.battery)
            continue
        # 이 부분에서 early continue를 하여서 연산량 감소 시킴
        elif batteries and now.battery > min(batteries):
            continue
        elif now.distance == n:
            batteries.add(now.battery)
            continue
        elif now.distance > n:
            continue
    
        if now.distance*2 <= n:
            q.append(Node(now.distance*2,now.battery))
        if now.distance+1 <= n:
            q.append(Node(now.distance+1,now.battery+1))
            
            
def solution(n):
    # global batteries, flag
    
    temp = n
    while temp > 1:
        if temp % 2 == 0:
            temp = int(temp/2)
            flag.add(temp)
        else:
            break
   
        
    bfs(n)
    return min(batteries)

풀이

1에서 n까지 bfs를 이용해서 모든 경우를 탐색하려고 했다.
이때 한번에 이동 가능한 거리를 1로 제한했는데, 이는 최소한으로만 배터리를 써서 도달하는 경우를 찾기 위함이었다. 그러나 이로 인해서 불필요한 노드가 많이 발생해서 주어진 시간 안에 문제를 풀 수 없었다.

즉, 최소한의 거리로만 움직이는 모든 경우를 따지기 때문에 최소 비용을 구할 순 있었지만 최소 거리로만 움직이기에 n까지 도달하는데 많은 경우의 수가 발생하게 된 것이다.

역방향 알고리즘 : n에서 1까지

def solution(n):
    answer = 0
    while True:
        if n == 0:
            break
        elif n % 2 == 0:
            n = int(n / 2)
        else:
            answer += 1
            n -= 1

    return answer

풀이

n에서 1까지 움직인다.
이때 최소 비용으로만 움직이기 위해서 한번에 n/2만큼 움직일 수 있으면 그냥 움직이지만, 그렇지 못하는 경우에는 한칸만 배터리를 사용해서 뒤로 간다. 이를 반복해서 최종적으로 0에 도달할 때까지 무한 반복한다.

깨달은 점

알고리즘이 너무 어렵게 느껴지면, 그것은 잘못된 접근이다. 인간이 주어진 시간 내에 풀 수 있도록 내기 때문에 어려울 수가 없다. 어렵다면 역발상을 해보자.

알고리즘이 너무 하드해지면 역발상하기!!