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

아!!짜증나!!! 효율성 테스트에서 자꾸 시간 초과나서 인터넷봄.. 답지보는건 자존심 상하는데.. 휴

 

실패한 내 코드

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

    return p[n]

이렇게 최솟값을 다 구해줘서 구했다. 하나하나씩 다 구해줘서 느린건 알겠는데.. 재귀로 해도 더느려지고 그래서 포기했었음 ㅠ

 

다른사람코드

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

    return answer

ㅠ 이거 보니까 진짜 짜증났다.. 왜 난 더어렵게 풀어서.. 휴... 알고보니 완전 쉬운 문제였음..

 

이 방식으로 푼걸 다르게 코드를 짜면 이렇게 된다.

def solution(n):
    answer = 1
    while n > 1:
        answer += n % 2
        n = n // 2
    return answer

신기방기

 

이진법으로 푼 방법도 있다. 이게 젤 천재같음

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

3이면 11 이렇게 된다. 이건 앞으로 2칸 걸어갔다는 의미이다. 즉, 1이 앞으로한칸 0이 *2이다.