Level2️⃣ - 점프와 순간이동

https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

 

다양한 예제를 시도해보면서 규칙을 찾아보았다.

그리고 재귀를 통해 구현할 수 있을 거 같다는 느낌이 들었다.

우선 N을 재귀로 계속 나누어본다.

D(8) ➡ D(4) ➡ D(2) ➡ D(1)

재귀함수의 인자값이 1이 되면 1을 리턴한다. 기저 조건에 해당한다. 처음에는 무조건 배터리를 한 개 소모하기 때문이다.

그리고 배터리 갯수를 누적하면 된다. D(1)에서 1이 리턴되고 D(2)는 2까지 가는데 필요한 배터리의 갯수인데 처음 소모한 배터리를 제외하고 배터리를 소모하지 않는다. 따라서 그대로 1이 리턴되고 D(4)도 처음 소모한 배터리를 제외하고 배터리를 소모하지 않으므로 그대로 1이 리턴되고 D(8)도 마찬가지이므로 총 배터리의 갯수는 1이 된다.

 

D(5) ➡ D(2) ➡ D(1)

위의 과정과 마찬가지로 D(1)은 1을 리턴하고 D(2)도 1을 그대로 리턴한다. 하지만 D(5)에서는 배터리가 한 개 필요하다. 때문에 반환되는 값에 1을 더한 후 반환해줘야한다. 이렇게되면 배터리의 갯수가 총 2개이다.

 

이 과정에서 찾을 수 있는 규칙은 N이 홀수이면 배터리가 무조건 한 개 더 필요하다는 것이다.

 

글로 적으니 모호하다. 그림으로 표현해보자.

재귀를 호출하는 과정을 가지를 뻗는다고 표현하고 값을 리턴하는 부분을 값을 수거한다고 생각해보자.

재귀함수를 호출하며 가지를 뻗어나간다. N=1이 된다면 1을 리턴한다. 그리고 값을 하나씩 수거해나간다. 콜스택에서 팝되는 과정이다. 가지의 맨 밑에서부터 팝된다. 수거해가면서 N이 짝수이면 1을 더하지 않고 그대로 위로 전달한다. N이 홀수라면 1을 더해서 전달한다.

이 경우에도 마찬가지이다. 다만 5는 홀수니까 수거할 때 1을 더해서 반환하면 된다.

 

코드

function solution(n){
    let cnt = 0;
    if(n === 1) return cnt + 1;
    else{
        if(n%2===1) cnt = solution(Math.floor(n/2)) + 1; 
        else cnt = solution(Math.floor(n/2));
    }
    return cnt;
}

 

사실 N을 2로 나누면서 나오는 나머지의 합을 구하면 된다. 하지만 재귀로 구현한 것에 뿌듯함을 느껴 정리해본다.