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

출처:: programmers.co.kr/learn/courses/30/lessons/12980?language=python3

분류::

 

1. 문제 이해 및 해결과정

거리  1   2  3  4  5  6  7         1   1  2   - 2 : 1이동 + 순간2 or 2이동   - 3 : 1이동 + 순간2 + 1이동   - 4 : 1) 4이동 2)   dp = min( dp[n//2] (나누어떨어질 경우) , n)  dp = min( dp[n-1] + 1 , n )

 

2. 풀이방법

 1. 

def solution(n):
    cnt=1
    
    while n>1:
        if n%2==0: #2로 나누어떨어지면
            n//=2
        else:
            n-=1 #숫자 짝수로 만들기
            cnt+=1

    return cnt

 2. 이진수로 바꿀 때, 1의 개수가 필요한 점프의 개수 

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

3. 몫과 나머지 이용 

def solution(n):
    cnt=0
    while n>0:
        q,r=divmod(n,2) #몫과 나머지 
        n=q
        if r==1:#나머지가 1이라면 
            cnt+=1
        
    return cnt

 

3. 오답원인

 1. dp 메모리 에러  n이 10억이므로

def solution(n):
    dp=[0]*(int(1e9))
    dp[1]=1
    for i in range(2,n+1):
        if i%2==0:#2로 나누어 떨어지면 그대로
            dp[i]=min(dp[i//2],i)
        else: 
            dp[i]=min(dp[i-1]+1,i)

    return dp[n]

 

 

4. 알게된 점

divmod : 정수를 나눈 몫과 나머지를 구하는 함수 

- divmod == a//b,a%b

- 작은 숫자를 다룰 때는 느리다