https://school.programmers.co.kr/learn/courses/30/lessons/12980
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 |
위의 예시와 같습니다.
처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동합니다. 이때 1 칸을 앞으로 점프하면 위치3으로 이동합니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 3) x 2 이동할 수 있으므로 위치 6에 도착합니다. 이 경우가 건전지 사용량이 가장 적으므로 2를 반환해주면 됩니다.
위와 같은 방식으로 합니다.
import java.util.*;
public class Solution {
public int solution(int n) {
int ans = 0;
String bina=Integer.toBinaryString(n);
int len=bina.length();
for(int i=0;i<len;i++){
if(bina.charAt(i)=='1'){
ans++;
}
}
return ans;
}
}
5000이 5가지인 것을 보고 이진수로 돌려보았는데 1의 개수가 5개였다.
그리고 순간이동은 현재까지 이동한 위치*2
로 순간이동을 하니까,
1, 2, 4, 8, 16 등..
은 모두 한 번만 점프를 하면 되는 것이다.
다른 풀이로는
while(n!=0){
if(n%2==0)
n=n/2;
else{
n=n-1;
ans++;
}
}
과 같은 풀이가 대다수였다!
짝수면 텔레포트를 하니까 배터리는 안쓰니 2로 나눠주고, 홀수이면 점프를 해야하니까 ans++를 해주었다.