[프로그래머스] 점프와 순간 이동

이 문제를 처음 보고 그냥 아무 생각없이 dp를 떠올렸다...

(근데 옛날에는 분명 dp였던 기억이.....?!!??!!!)

dp로 풀 수 없는 이유는 아래와 같이 10억이라면 dp로 하더라도 10번은 가봐야 아는 문제이다....

내가 푼 잘못 푼 풀이

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

문재 풀이는 다음과 같다.

거꾸로 2로 나눠가면서 구하면 된다. 2로 안 나눠지면 점프가 필요한 거니까 건전지 사용 +1

def solution(N):
    result = 0
    while N > 0:
        result += N % 2 # 만약에 n = 3 이면 result +1 하고
        N //= 2			#n=1이 된다. (점프하고 2 나누기[순간이동])
    return result

추가적으로 조금 더 발전시키면 

4 = 100 , 8 = 1000 처럼 2의 n 제곱이면 처음 0 ->1 빼고 순간이동으로 갈 수 있다.

이를 이진수로 표현해 보면 1이 하나인 이진수이다.

즉, 건전지 사용량은 이진수로 변환했을때 1의 개수와 같다. (대체 이건 어떻게 생각한걸까...)

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