[프로그래머스][점프와 순간 이동] DFS를 사용하지 않는 풀이

https://school.programmers.co.kr/learn/courses/30/lhttps://school.programmers.co.kr/learn/courses/30/lessons/12980#essons/12980#

프로그래머스

문제에 대한 이해:

위치 0부터 점프나 순간이동을 해서 목적지 N까지 도달한다.

점프를 할 경우 한 칸을 점프할 때마다 배터리가 하나씩 소모된다. 예를 들어 3칸을 점프했다면 소모된 배터리는 3이다. 

순간이동을 할 경우 현재까지 이동한 거리 즉. 현재 인덱스에서 2배가 된 인덱스'로' 이동할 수 있다.

배터리 소모를 최소화하며 이동할 경우 최소 배터리 소모량을 구하라.

 

 

이 문제를 정리하는 이유:

1. 문제 자체는 평이하나 문제를 잘못 이해하여 푸는데 시간이 과하게 걸렸다.

순간 이동을 할 경우 현재까지 이동한 거리에서 두 배를 한 '거리'만큼 이동하는 것이라 생각했다.

문제의 순간 이동: 현재 위치가 4라면 8로 이동한다.

나의 이해: 현재 위치가 4라면 8칸을 이동하여 12로 이동한다.

문제를 다시 한번 더 꼼꼼히 읽고 파악해야 한다는 것을 실감했다.

 

2. DFS, BFS를 사용하지 않아도 되는 경우이라는 것을 간과

N이 십 억까지도 입력되는 문제에서 DFS나 BFS를 사용하면 시간 초과 에러가 날 것이나 문제에 대해 정확히 이해하지 못해 DFS로 계속 풀이하려 했다. 

 

문제풀이:

풀이는 매우 간단하다. 순간이동을 할 경우 배터리 소모가 0이기 때문에 N의 값이 짝수일 경우 N은 N/2(짝수이므로 N/2와 N//2의 값이 같다.)가 되고

N이 홀수일 경우 N은 N-1이 된다. N-1을 할 때만 배터리가 소모되므로 이 때마다 배터리 소모량 + 1을 해주고 N == 0 이 되면 총 배터리 소모량을 리턴해주면 된다.

 

예시코드: 

def solution(n):
    ans = 0
    while n > 0:
        if n % 2 == 0:
            n /= 2
        else:
            n -= 1
            ans += 1
    return ans