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

문제요약

• 순간이동 비용 : 무료
• k만큼의 점프 비용 : k
• 순간이동을 하고자 할 때는 (현재까지 온 거리) x 2 에 해당하는 위치로만 순간이동을 할 수 있습니다.
• 점프와 순간이동의 제한 횟수는 없습니다.

n 거리에 도달하고자 할 때 최소 비용을 구하시오.

아이디어

사실 그냥 답을 봤다... 2진수로 표현한 뒤 1의 수를 세면 된다고 한다.
2로 나누는 과정이 텔레포트고 나머지가 1이 생긴다면 텔레포트 위치를 조정하기 위해 점프를 1칸씩 하는 과정이라고 하는데... 이게 최적해인 이유는 사실 잘 모르겠다.

최대한 텔레포트를 사용하는 게 최적해를 찾는 과정이겠거니.. 할 뿐이다.

소스코드

py

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

cpp

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans = 0;

    while(n>1){
        ans+=n%2;
        n = n/2;
    }
    ans+=n;
    return ans;
}