OO 연구소는 한 번에 K
칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K
칸을 점프하면 K
만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N
만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N
이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.
예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.
위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.
N
: 1 이상 10억 이하의 자연수K
: 1 이상의 자연수N | result |
---|---|
5 | 2 |
6 | 2 |
5000 | 5 |
function solution(n) {
let result = 0;
while(n) {
if (n % 2 === 0) {
// 2로 나누어 지면 걸음 수 그대로
n /= 2;
} else {
// 2로 나누어 지지 않으면 점프
n--;
result++;
}
}
return result;
}
// 코드를 작성해보니 익숙한 구조인게 느껴진다.
// 고민해보니 2진수에서 1의 개수를 구하면 된다
function solution(n) {
// 2진수로 변경 후 정규식으로 0을 제거한 길이
return n.toString(2).replace(/0/g, "").length;
}