점프와 순간이동

접근 방식(알고리즘 분류)

• 연산문제

내 풀이

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

풀이 설명

• 5000 --> 2500 --> 1250 --> 625 --> 624 --> 312 --> 156 --> 78 --> 39 --> 38 --> 19 --> 18 --> 9 --> 8 --> 4 --> 2 --> 1
• 1을 빼줄때만 +1을 해줌

느낀점

• 1에서 5000으로 올라갈때 최대한 빨리 올라가려고 재귀함수를 통해 5000에 가장 가까운 위치까지 간 후 백트래킹을 통해 조건을 만족시키려고 했다.
• 문제를 너무 어렵게 접근한 것 같다.
• 1에서 부터 시작해서 5000으로 가는 것이 아니라 5000에서 시작해서 1로 가는 풀이가 더 쉬운 접근인것 같다.
• 하지만 반대로이기 때문에 2로 나누어지지 않을 경우 1을 더해주는 것이 아니라 빼줘야한다.