링크
https://school.programmers.co.kr/learn/courses/30/lessons/12980
문제
주어진 거리 n을 이동하는데 점프와 순간이동을 진행할 수 있다. 점프를 하게되면 원하는 거리만큼 이동이 가능하지만 거리가 k라면 k 만큼의 에너지를 사용한다. 순간 이동을 하게되면 현재 위치의 2배만큼 앞으로 이동이 가능하다. 원하는 거리 n까지 이동하는데 최소로 사용한 에너지는 얼마인가?
예제로 이해
거리 n = 6일 때를 기준으로 설명하겠다.
1칸 점프 => 사용에너지 1 현재위치 1
순간 이동 => 사용에너지 1 현재위치 2
1칸 점프 => 사용에너지 2 현재위치 3
순간이동 => 사용에너지 2 현재위치 6
총 2만큼의 에너지를 사용하여 이동이 가능하다.
문제를 풀기 위한 코드를 짜기위해서는 주어진 거리에서 반대로 접근을 해야한다.
n / 2를 진행하여 해당 값이 정수인지 판별하여 정수라면 순간이동을 사용한 것으로 생각한다. n = 3일 때, n / 2를 진행하면 정수가 아닌 수가 나오게 되는데 이때는 1칸 점프한 것으로 간주하여 n = n - 1을 진행하고 에너지를 1만큼 사용한 것으로 한다.
이 과정을 n = 1이 될 때 까지 반복을 하면 사용한 에너지가 얼마인지 구할 수 있다.(n = 1일때는 무조건 에너지 1을 사용한 것으로 간주하여 에너지 자체를 선언할 때 1로 선언한다.)
코드
function solution(n) {
let energy = 1
for(; n !== 1;) {
if(parseInt(n / 2) !== n / 2) {
n = n - 1
energy++
} else {
n = n / 2
}
}
return energy
}코드 풀이
시작할 때 무조건 1칸은 점프를 진행하는 것으로 생각해서 에너지의 선언 자체를 1로 선언한다.
그 후 위에서 적은 내용처럼 원하는 위치에서 반대로 생각을 해주는데 n = 1이 오기 전까지 반복을 진행한다.
반복문 내부에는 n / 2를 진행한 값이 정수인지 아닌지를 비교하여 정수라면 순간이동을 사용한 것으로 생각하고, 정수가 아니라면 점프를 한 것으로 생각하여 n = n - 1을 진행하고 에너지에 1을 더해준다.
반복이 종료되면 구한 에너지 값을 반환한다.
다른 풀이
위에 정리한 코드는 문제 자체를 점프와 순간 이동의 관점에서 접근한 방법이고, 이 문제는 다르게 풀이가 가능하다.
주어진 수 n을 2진수로 표현하면 0과 1로 구성이 될텐데 여기서 1의 갯수를 세면 된다.
6을 2진수로 나타내면 110(2) 이므로 1의 갯수는 2개이다. 따라서 사용한 에너지는 2이다.
5000을 2진수로 나타내면 1001110001000(2) 이므로 1의 갯수는 5개이다. 따라서 사용한 에너지는 5이다.
