프로그래머스 / 정수론 / 점프와 순간 이동

문제

---

 

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

프로그래머스

 

입출력

---

 

해설

---

 

총 N만큼의 거리를 걸어갈 것인데, 다음과 같이 움직인다.

 

1. K만큼 점프한다.

2. 지금까지 움직인 거리만큼 * 2 움직인다.

 

1번을 움직임은 K만큼의 에너지를 소비하게 되고, 2번 움직임은 에너지를 소비하지 않는다.

 

에너지를 최소한으로 소모하여 N을 만들어야 할 때 무조건 1번 아니면 2번을 선택해야 된다면

1번보다는 2번을 최대한 움직이는 것이 에너지를 아예 소모하지 않기에 이득이라는 것을 알고 있다.

 

그러면 2번을 최대한 움직이고 나머지를 1번으로 움직이면 되지 않을까?

 

정답이다. 하지만 최대한 움직이고 1번으로 움직이는 것을 정하는 것은 매우 어려운 일이다.

 

고로 이 문제는 N에서 부터 거꾸로 0을 만들어주면 된다.

 

만약 n이 홀수라면 1을 빼주고 짝수라면 ÷ 2를 해서 1을 빼준 횟수만 세어주면 된다.

 

 

정답코드

---

'''
'25. 08. 11

1. 한 번 K 칸앞으로 점프 K만큼의 건전지사용
2. 현재까지 온 거리 x2 순간이동 건전지 x

2배를 움직이면 건전지를 사용하지 않기 때문에 최대한 2배를 많이 움직이는 것이 좋다.
그렇기 때문에 최대한 2배씩 움직이게끔 하고
홀수있때만 1씩 움직이는 것이 최소가 될 수 밖에 없다.
'''
def solution(n):
    ans = 0
    while n:
        ans += n&1
        n>>=1
    return ans

 

깃허브 : https://buly.kr/ESytsLI

유튜브 : https://youtu.be/xbVtNqjlQvk