Codility Java Ladder

문제

Link

코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int[] solution(int[] A, int[] B) {
        int[] result = new int[A.length];
        int[] fibonacci = getFibonacci(A.length);
        for (int idx = 0; idx < A.length; idx++) {
            result[idx] = fibonacci[A[idx]] % (1 << B[idx]);
        }
        return result;
    }
    private int[] getFibonacci(int length) {
        int[] fibonacci = new int[length + 2];
        fibonacci[1] = 1;
        fibonacci[2] = 2;
        for (int idx = 3; idx <= length; idx++) {
            fibonacci[idx] = (fibonacci[idx - 2] + fibonacci[idx - 1]) % (1 << 30);
        }
        return fibonacci;
    }
}

설명

1. 주어진 배열 A의 크기 + 2만큼 피보나치¹ 수열을 생성한다.
   • 피보나치 수열의 초기화와
   • 피보나치 수열은 0, 1, 1, 2, …로 시작하지만, 불필요한 중복되는 1은 제외하고 구성한다.
   • 단, 1 « 30(= 2 ^ 30)을 사용하여 오버플로를 방지하면서 결과 값이 동일해지는 역할을 수행한다.
2. 주어진 배열 A의 크기만큼 반복하여 구한 피보나치 수열의 결과를 활용해 A[idx] 길이의 사다리를 B[idx] 횟수로 올라갈 수 있는 방법의 수를 구하여 결과를 저장하는 변수 result[idx]에 넣는다.
   • 피보나치 값의 A[idx]번째 있는 값은 진행 가능한 횟수를 의미하며, 해당 값을 1 « Bidx로 나눈 나머지 값이 실제 사다리 꼭대기에 오르는 방법의 수이다.
3. 반복이 끝나면 주어진 배열 A와 B의 각 요소 별 사다리 꼭대기에 오르는 방법의 수를 저장한 변수 result를 주어진 문제의 결과로 반환한다.

결과

Link

소스

Sample Code는 여기에서 확인 가능합니다.

Reference

1. Wiki-Fibonacci_Numbers ↩