점프와 순간 이동

풀이

처음 이 문제를 보곤 음... 재귀로 풀면 풀릴듯? 하고 아래처럼 풀었다.
그래서 문제를 재귀로 풀면서 2가지로 나누는 구간을 생성하고 나눠줬다.

# 00 연구소는 한 번에 k칸을 앞으로 점프, (현재까지 온 거리)*2에 해당하는 위치로 순간이동 가능
# 순간이동은 건전지 사용 줄지않음
# k칸을 점프하면 만큼의 건전지 사용
# N만큼 떨어져 있는 장소로 감. 점프 이동은 건전지 효율때문에 최소로.

# 재귀함수를 이용해봐야 할 듯
min_battery = 0
def go_to(now, n, battery):
    global min_battery
    # min_battey가 사용된 battery보다 크면 battery값 적용
    if min_battery <= battery:
        return
    # 목표 위치에 도달하면
    if now == n:
        if min_battery > battery:
            min_battery = battery
        return
    #2가지 방법이 있음. 1은 1칸씩 움직이기, 2는 현재 위치 2배로 넘어가기
    else:
        # 1칸씩 움직이기
        go_to(now+1, n, battery+1)
        # 현재 위치 2배로 넘어가기
        if now !=0 and now*2 <= n:
            go_to(now*2, n, battery)    
    return

def solution(n):
    global min_battery
    # 배터리 사용 최솟값을 최대 사용량으로 초기화
    min_battery = n+1
    
    go_to(0, n, 0)

    return min_battery

이런 함수 깊이 문제로 재귀로는 풀수가 없었다.
만약 된다해도 시간문제가 있지 않았을까 싶기도 하다.

그러다가 어.....어... 어. 2의 배수 나머지
로 해서 아래처럼 풀렸다.

def solution(n):
    battery = 0
    # 2배로 움직이니까 2를 가지고 움직이자.
    while n > 0:
        if n % 2 == 0:
            n = n // 2
        else:
            n -= 1
            battery += 1
        
    return battery

진짜 문제 많이 풀고 공부 많이 해야겠다.
예전에 어떻게 이거 그냥 뚝딱 생각하고 푼거지...

다른 사람 풀이

아니 이거 뭐냐고... 똑똑한 사람 너무 많아.
흑흑흑 오늘도 다른 사람 풀이보면서 자존감 박살 중
나도 이렇게 풀 수 있는 사람이 될 수 있을 때까지 버텨내야지.

def solution(n):
    return bin(n).count('1')