[파이썬] 점프와 순간 이동 - Summer/Winter Coding(~2018) [CODING TEST #58]

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

 

 

동적계획법(DP)을 이용하여 풀 수 있다.

아래서부터 위로 채워가는 Bottom - Up 방식을 이용하면 런타임 에러가 난다. n만큼 반복문을 돌아야 하는데 n의 크기가 최대 10억이기 때문이다. 문제가 풀리긴 하니 작은 입력 크기에서 사용해야 함.

 

# Bottom-Up
def solution(n):
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2,n+1):
        if i%2 == 1:
            dp[i] = dp[i-1]+1
        else:
            dp[i] = min(dp[i-1]+1,dp[int(i/2)])
    
    return dp[n]

 

Top - Down 방식을 이용하면 짝수마다 2로 나누므로 효율성 테스트까지 통과할 수 있다.

 

# Top-down
def solution(n):
    ans = 0
    while n != 2:
        # n == 1일 때
        if n == 1:
            return 1
        # n이 짝수일 때, 슈트 이용
        elif n % 2 == 0:
            n //= 2
        # n이 홀수일 때, 건전지 소모
        elif n % 2 == 1:
            n -= 1
            ans += 1
    ans += 1
    return ans