점프와 순간 이동→재귀함수(DFS)★★ + 동적 계획법

효율성 실패한 나의 첫번째 풀이 

def solution(n):
    if n == 1 or n == 2:
        return 1
    
    result = [0] * (n + 1)
    result[1] = 1
    result[2] = 1
    
    for i in range(3, n+1):
        # 이전에 구한 결과값을 재사용
        if i % 2 == 0:
            result[i] = result[i // 2]
        else:
            result[i] = result[i-1] + 1
    
    return result[n]

▶ for문 때문에 작은 수부터 큰 수까지 쭈욱 훑어서 효율성 테스트에서 계속 실패했다. 

 

 

효율성 테스트를 통과한 풀이 

def solution(n):
    if n==1 or n==2:
        return 1
    if n % 2 ==0:
        return solution(n//2)

    else:
        return solution(n-1)+1

▶ n/2를 위 코드에 사용했을 때는 효율성 테스트를 못했는데,
    n//2를 위 코드에 사용했을 때는 효율성 테스트에 통과를 했음 

 

▶ 필요한 함수만 스캔해서 리턴값을 반환받자!!!