[프로그래머스 LV.2] 점프와 순간이동 (feat.그리디)

프로그래머스 점프와 순간이동 문제 (lv.2)

 

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

프로그래머스

 

고려 사항

문제에서 요구하는 사항이 "최소한의 점프"를 통해 건전지 사용량을 최소화하는 것이다.  아마 그리디 유형?!?!

 

그로인해 고려할 것 , 

1.순간 이동은 건전지 소모하지 않으므로, 순간이동을 최대한 활용

2. 점프는 반드시 필요한 경우에만 수행하며 건전지 사용량 최소화 

 

 

 

문제풀이 

 

 

def solution(n):
    #아이언슈트 순간이동-건전지X 점프:건전지 필요
    #k+ : 점프, x2:순간이동
    # N만큼 떨어진곳으로, 점프는 최소한으로 , 건전지 사용량의 최소값 구하기 
    0
    ans = 0
    while n>0:
        if n%2==0: #짝수라면 점프
            n//=2
        else: #홀수라면 
            n=n-1
            ans+=1
    return ans

 

문제를 읽으면서 어떻게 경우를 나누는게 좋을까 고민했는데,

홀수인 숫자에는 순간이동만으로 갈 수 없으니까 홀짝으로 구분을 해서 문제를 풀었다.

홀수일경우에는 건전지 사용량을 카운트 하고, 짝수에서는 순간이동을 할 수 있도록 구현했다.

 

O(logN)의 시간 복잡도를 가짐 

 

 

끝!