Codility Lesson13 - Ladder

🔍 문제

---

 

어떤 사다리가 있고, 발을 밟고 올라갈 수 있는 발판이 N개가 주어진다. 이때 발판을 한번에 이동할 수 있는 칸의 수는 1칸 아니면 2칸만 허용된다. 예를들어, 3개의 발판을 가진 사다리를 올라가서 꼭대기에 도달할 수 있는 방법은 [1, 1, 1] or [1, 2] or [2, 1] 로 세가지이며 4개의 발판을 가진 사다리를 올라가서 꼭대기에 도달할 수 있는 방법은 [1, 1, 1, 1] or [1, 1, 2] or [1, 2, 1] or [2, 1, 1] or [2, 2]로 5가지 방법이 존재한다.

 

따라서 주어진 사다리를 올라갈 수 있는 경우의 수를 return하면되는데, 발판의 수가 커질 수록 그 경우의 수는 기하급수적으로 커지기 때문에 배열 B에 주어진 수를 이용해서 2^B[i]를 한 값으로 경우의 수를 나누어서 return 하도록 한다.

 

Test results - Codility

 

✏️ 풀이 - JS

---

사다리의 발판 수에 따른 경우의 수는 피보나치 수열을 이룬다. 발판에 따른 경우의 수는 다음과 같다.

[0, 1, 2, 3, 5, 8, 13 ...]

 

따라서 발판의 수에 따른 경우의 수 배열을 미리 만들어 둔 후, A배열과 B배열을 돌면서 미리 만들어준 fibonacci[i]배열을 이용해서 return 값을 구하면 된다.

 

중요한 것은 피보나치 수열을 구할때 fibonacci[i] = (fibonacci[i-1] + fibonacci[i-2]) % max;로 마지막에 max값으로 나누어준 부분인데, 만약 이 부분에서 max로 나누지 않으면 submit했을 때 test에 통과하지 못한다.

 

왜냐하면 문제에 따르면 L의 범위는 1부터 50,000까지인데 만약 L값이 50,000이 들어오면 50,000번째 피보나치 수열을 구하는데에는 최대 12초 이하까지 걸릴 수 있다고 한다. 그리고 숫자 자체도 어마어마하게 커져 overflow가 일어나 이 부분을 안전하게 잡아줄 수 있는 장치가 필요하게 되는데, 그 장치가 max값인 것이다.

 

max값은 B[i]가 될 수 있는 가장 큰 값이 30이기 때문에, 2^30인 값이다.

 

따라서 피보나치 수들을 max로 나눈 나머지를 저장한 후, 이를 이용해서 result 값을 구해서 반환해준다.

function solution(A, B) {

    const L = A.length;
    const max = Math.pow(2, 30);

    const fibonacci = [0, 1, 2];

    for(let i = 3; i < L+1; i++) { // L까지 피보나치 수열(방법의 수) 구해놓기
        fibonacci[i] = (fibonacci[i-1] + fibonacci[i-2]) % max;     
    }

    const result = [];

    for(let i = 0; i < L; i++) { // 2^B[i]의 수로 나누기
        result[i] = fibonacci[A[i]] % Math.pow(2, B[i]);    
    }

    return result;
}