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

문제 링크

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

문제 설명

문제 풀이

- 처음에는 현재 위치에서 +1 칸을 이동하고 count도 1증가시키거나 *2칸을 이동하고 count는 증가시키지 않도록 하여 큐에 추가하는 방식인 BFS로 풀었으나 시간초과가 발생했다. 

from collections import deque
def solution(n):
    ans = n
    queue= deque([(1,1)])
    while queue:
        val = queue.popleft()
        if val[1] >=n : continue
        if val[0] >n: continue
        elif  val[0] == n :
            if val[1] < ans: ans = val[1]
        queue.append((val[0]*2,val[1]))
        queue.append((val[0]+1,val[1]+1))

    return ans

 

 

- 그래서 문제 풀이를 위한 수학적 방식이 있지 않을까 고민해 본 결과 아래와 같은 코드를 작성하여 정답을 맞췄다.

EX) 5000 -> 2500 -> 1250 -> 625 -> 624(count+=1 ) -> 312 -> 156 -> 78 -> 39 -> 38(count+=1) -> 19

-> 18( count+=1) -> 9 -> 8( count+=1)  ->4->2->1->0( count+=1)  종료 count = 5

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

다른 사람의 풀이

- 아래 풀이의 경우 n을 이진수로 바꾸어 1의 개수를 세어 주는 방식으로 코드를 작성했다

- 정말 깔끔한 풀이인 것 같다.

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