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

문제 확인

프로그래머스

나의 풀이

• 나머지를 활용한 풀이
  • 비용을 줄이려면 가능하면 항상 순간 이동을 해야 한다.
  • $n$ 번째 위치는 $n // 2$에서 순간 이동해서 바로 가거나, 순간 이동 후 1 만큼 점프하여 갈 수 있다.
  • 따라서 매번 2 로 나눴을 때, 나머지가 1인 경우에만 비용을 추가하면 된다. 

def solution(n):
    answer = 0
    while n:
        q,r = divmod(n, 2)
        # 점프가 필요할 때 비용 추가
        if r == 1:
            answer += 1
        n = q
    return answer

• DP를 활용한 풀이
  • $n$의 범위가 10억이라서 시간 초과가 발생 했지만, DP로도 접근할 수 있는 문제다.

def solution(n):
    answer = [i for i in range(n + 1)]
    answer[0] = 1e9
    for i in range(2, n + 1):
        # 짝수일 경우
        if i % 2 == 0:
            answer[i] = min(answer[i], answer[i // 2])
        # 홀수일 경우
        else:
            answer[i] = min(answer[i], answer[i // 2] + 1)
    return answer[-1]

다른 사람 풀이

• 2 진법으로 변환된 수는, 매번 2로 나눴을 때의 나머지를 활용해서 나타낸다. 
• 나머지가 1일 때만 가격을 계산하면 되기 때문에, 가격은 이진법 표현의 1의 개수를 세서 확인할 수 있다.

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

 

 

프로그래머스