programmers. 점프와 순간 이동

문제

문제

풀이

우선 제자리에서 순간이동을 해봤자 0*2이기 때문에 무조건 한 칸 점프를 해야한다

그렇기 때문에 거리 1에 가기위한 최소값은 1

거리 2에 가기위해서는 순간이동으로 가능하기 때문에 거리 2에 가기위한 최소값은 그대로 1

거리 3에는 순간이동으로는 갈 수 없는데 3이 홀수이기 때문에 *2를 하는 순간이동의 특성상 불가능하다

그래서 거리 2에서 점프를 해야하기 때문에 거리 3의 최소값은 2

여기까지만 적어보고 dp 풀듯이 풀면되겠다 싶었다

인덱스를 거리로 하고 벨류를 소모되는 에너지로 하는 배열을 만들어서 바텀업 방식으로 구현해서 제출했다

코드 1

function solution(n) {
    const battery = [0,1,1];
    for(let i =3; i<=n;i++){
         battery[i] = (i%2===0) ? battery[i/2] : battery[i-1]+1;
    }

    return battery[n];
}

실패

정확성 테스트는 다 통과했는데 효율성 테스트에서 전부 시간초과가 걸렸다

생각해보니 바텀업으로 풀어나갈 필요가 없었다 *2로 그 사이의 인덱스를 훌쩍 뛰어넘을 수 있는데 하나하나 구해가는건 매우 비효율적이었던 것

그래서 탑다운 방식으로 풀었는데

1. n이 2로 나누어떨어지는지 확인

2. 나누어 떨어진다면 n/2를 해서 이동 거리를 반 줄인다

3. 나누어 떨어지지 않는다면 n--을 해서 한 칸 점프한다 점프를 했으니 소모되는 에너지 변수를 생성한 뒤 +1 해준다

4. 다시 1번으로 돌아간다

코드

function solution(n) {
    const battery = [0,1,1];
    let cnt = 0;
    while (!battery.includes(n)) {
        if (n % 2 === 0) {
            n = n / 2;
            continue;
        }
        n--;
        cnt++;
    }

    return battery[n]+cnt;
}

정확성과 효율성 모두 통과했다

이런 풀이에 의구심이 들어서 다른 사람들의 풀이를 봤는데 간단하게 n을 이진수로 변환한 뒤 1의 개수를 세어주면 되는 문제였다

while 반복문안에서 하는 행위가 n을 이진수로 바꾸는 과정에서 1이 나올 때 cnt에 1을 더해주는게 완전히 동일하기 때문..

위 코드는 사실 dp형식이 전혀 필요가 없었다

function solution(n) {
    let cnt = 0;
    while (n>0) {
        if (n % 2 === 0) {
            n = n / 2;
            continue;
        }
        n--;
        cnt++;
    }

    return cnt;
}