Level 2 ) 점프와 순간 이동 ⭐️

Doozuu·2023년 3월 27일
0

프로그래머스 (JS)

목록 보기
101/183

문제 설명

OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.

예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.

처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.
위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.

제한 사항

숫자 N: 1 이상 10억 이하의 자연수
숫자 K: 1 이상의 자연수

입출력 예

N		result
5		2
6		2
5000	5

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동합니다. 이때 1 칸을 앞으로 점프하면 위치3으로 이동합니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 3) x 2 이동할 수 있으므로 위치 6에 도착합니다. 이 경우가 건전지 사용량이 가장 적으므로 2를 반환해주면 됩니다.

입출력 예 #3
위와 같은 방식으로 합니다.

풀이

건전지 사용량을 최소화하려면 순간 이동을 최대화해야 한다.
처음 위치에서부터 이동 방법을 고려하면 가능한 케이스가 많아서 어려우므로, greedy algorithm에 따라 도착 위치에서부터 고려하면 훨씬 간단해진다.

순간 이동은 2배씩 이동하는 것이므로 순간 이동이 가능하면(거리가 2로 나누어 떨어지면) 순간 이동을 해주고, 그렇지 않으면(거리가 2로 나누어 떨어지지 않으면) 한 칸 점프하여 다시 순간 이동이 가능한지 체크해주면 된다.

따라서 n이 0이 될 때까지 다음과 같은 시행을 반복해주면 된다.

  • 2로 나누어 떨어지면 2로 나누기
  • 2로 나누어 떨어지지 않으면 거리에서 1을 빼고, 건전지 사용량 1 더하기.

ex. n = 5 일 때,
1. 5는 2로 나누어 떨어지지 않으므로 1을 빼서(점프) 4로 바꾸고, 배터리 사용량을 1 증가시킨다.
2. 4는 2로 나누어 떨어지므로(순간 이동) 남은 거리는 2가 되고 배터리 사용량은 증가되지 않는다.
3. 2는 2로 나누어 떨어지므로(순간 이동) 남은 거리는 1이 되고 배터리 사용량은 증가되지 않는다.
4. 1은 2로 나누어 떨어지지 않으므로 1을 빼서(점프) 0으로 바꾸고, 배터리 사용량을 1 증가시킨다.
남은 거리가 0이 되었으므로 반복문은 종료되고, 배터리 사용량의 최솟값은 2가 된다.

function solution(n){
    let battery = 0;
    while(n > 0){
        if(n % 2 === 0){
            n /= 2;
        }else{
            n--;
            battery++;
        }
    }
    return battery;
}

신박한 풀이

2로 나누어 떨어지지 않는 수들의 갯수를 구하면 되므로, n을 이진수로 바꾼뒤 1의 갯수를 세서 구할 수도 있다.
(이진수는 어떤 수를 2로 나누고, 그 몫을 2로 나눈 나머지들을 쭉 나열한 것이다. 0이면 2로 나누어 떨어지는 것이고, 1이면 2로 나누어 떨어지지 않은 것이다. 따라서 어떤 수를 이진수로 변환한뒤 1의 갯수를 세면 2로 나누어 떨어지지 않은 수들의 갯수를 구한 것과 같다.)
ex. 5를 이진수로 변환하면 101이고, 1의 갯수를 세면 2이다.

function solution(n){
    return n.toString(2).match(/1/g).length;
}

참고 : https://jsikim1.tistory.com/272

profile
모든게 새롭고 재밌는 프론트엔드 새싹

0개의 댓글