[알고리즘] 프로그래머스 점프와 순간 이동 - Python

문제 : 프로그래머스 점프와 순간 이동 문제

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

프로그래머스

 

이 문제는 봤을 때 dfs 혹은 dp로 풀어야겠다는 생각을 했다. 더 접근이 쉬운 dp로 먼저 풀어보았다. 

 

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

 

이 풀이로 했을 때 효율성 테스트에서 걸렸다. 그 이유를 생각해보니 다음과 같은 문제가 있었다.

• n이 큰 경우 dp 배열 초기화에 메모리 낭비가 크다
• n이 큰 경우 for 문으로 n회를 반복하며 찾아나간다.

따라서 효율성 테스트에서는 메모리적인 측면과 시간적인 측면에서 걸렸다고 생각했다. 그래서 이 부분을 개선하기 위해서는 n까지의 모든 경우를 반복하는 것이 아니라 필요한 부분만 찾아나가야 한다고 생각했다.

 

역으로 n에서 1을 만드는 경우를 생각해보았다.

만약, n이 짝수인 경우에는 2를 계속 나누어서 홀수를 만든다. 그리고 그 때가지의 배터리 낭비는 없다. 

만약, n이 홀수인 경우에는 -1을 하고 배터리 소모 1을 추가하고, 다시 2를 계속 나누어서 홀수를 만든다. 이 과정을 반복하다보면 1이 되고 그때의 답을 구하면 된다.

 

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

 

훨씬 단순하고 구현이 쉬운 로직이다. 이 코드로는 테스트 케이스 모두를 통과했다. 이 문제로 얻을 수 있었던 것은 dp 배열을 초기화할 때 무조건 n 크기로 하던 습관을 다시 돌아봐야겠다는 것이었다.