Lesson 13. Fibonacci numbers - Ladder

1. 문제

You have to climb up a ladder. The ladder has exactly N rungs, numbered from 1 to N. With each step, you can ascend by one or two rungs. More precisely:
  - with your first step you can stand on rung 1 or 2,
  - if you are on rung K, you can move to rungs K + 1 or K + 2,
  - finally you have to stand on rung N.

Your task is to count the number of different ways of climbing to the top of the ladder.

For example, given N = 4, you have five different ways of climbing, ascending by:
  - 1, 1, 1 and 1 rung,
  - 1, 1 and 2 rungs,
  - 1, 2 and 1 rung,
  - 2, 1 and 1 rungs, and
  - 2 and 2 rungs.

Given N = 5, you have eight different ways of climbing, ascending by:
  - 1, 1, 1, 1 and 1 rung,
  - 1, 1, 1 and 2 rungs,
  - 1, 1, 2 and 1 rung,
  - 1, 2, 1 and 1 rung,
  - 1, 2 and 2 rungs,
  - 2, 1, 1 and 1 rungs,
  - 2, 1 and 2 rungs, and
  - 2, 2 and 1 rung.

The number of different ways can be very large, so it is sufficient to return the result modulo 2P, for a given integer P.

Write a function:
  vector<int> solution(vector<int> &A, vector<int> &B);

that, given two non-empty arrays A and B of L integers, returns an array consisting of L integers specifying the consecutive answers; position I should contain the number of different ways of climbing the ladder with A[I] rungs modulo 2B[I].

For example, given L = 5 and:
A[0] = 4    B[0] = 3
A[1] = 4    B[1] = 2
A[2] = 5    B[2] = 4
A[3] = 5    B[3] = 3
A[4] = 1    B[4] = 1
the function should return the sequence [5, 1, 8, 0, 1], as explained above.

Write an efficient algorithm for the following assumptions:
  - L is an integer within the range [1..50,000];
  - each element of array A is an integer within the range [1..L];
  - each element of array B is an integer within the range [1..30].

 

사다리 오르는 방법을 세는 문제.

단순히 사다리 오르는 방법만을 구하는 것이 아니라, 아래 공식으로 결과를 구해야 한다.

 

공식

결과 = (사다리 오르는 방법 개수) modulo \( 2^{p} \)

 

매개변수

Vector A : 사다리의 가로 다리 수 (사다리의 가로 다리 수에 따라 오르는 방법의 개수가 달라진다.)

Vector B : P

 

2. 매개변수 조건

Vector A 값 범위 : 1 ~ 50,000

Vector B 값 범위 : 1 ~ 30

 

3. 예제 분석

Vector A 값(N) (사다리의 가로 다리 수)	사다리 오르는 방법
4	1, 1, 1, 1	5개
	1, 1, 2
	1, 2, 1
	2, 1, 1
	2, 2
5	1, 1, 1, 1, 1	8개
	1, 1, 1, 2
	1, 1, 2, 1
	1, 2, 1, 1
	2, 1, 1, 1
	2, 1, 2
	2, 2, 1
	1, 2, 2

 

사다리 오르는 방법의 개수는 피보나치 수와 연관 있다. (0, 1, 1, 2, 3, 5, 8, 13 ... )

N	1	2	3	4	5	...
사다리 오르는 방법	1	2	3	5	8	...

 

 

4. 문제풀이 전략

• 1 ~ 50000까지의 피보나치 수를 구한다. 
• (A[i]번째 피보나치 수) modulo \( 2^{B[i]} \)를 계산한다.

 

5. 문제점 및 해결 방법

이 문제는 매우 간단하다.

사다리 오르는 방법이 피보나치 수와 관련 있음을 알아채는 것도 어렵지 않다. (문제가 피보나치 수이므로)

문제는 피보나치 수가 너무 크다는 것이다. 큰 수를 어떻게 저장할 것인가? 이것이 문제다.

 

4byte int 자료형이 표현할 수 있는 가장 큰 피보나치 수는 Fib(46) = 1,836,311,903

8byte int 자료형이 표현할 수 있는 가장 큰 피보나치 수는 Fib(92) = 7,539,532,410,122,121,396

위의 값이 정확한지는 모르겠으나, 어째든 F(50000)이라는 수를 일반적인 자료형으로 표현할 수 없음은 확실하다.

이를 해결하기 위해서는 나머지 연산자의 특성을 이해해야 한다.

 

결과 값의 범위

해답을 구하기 위한 공식은 다음과 같다.

Fib(N) modulo \( 2^{B[i]} \)

 

여기서 매개변수 조건에 따라 \( 2^{B[i]} \)의 최대 값은 \( 2^{30} = 1,073,741,824 \) 이다.

즉, 결과 값은 0부터 1,073,741,823 사이의 값이 되고, 이 값은 4byte int 자료형으로 표현가능한 값이다.

 

나머지 연산자에 대한 고찰

나머지 연산자는 자신의 자릿수보다 낮은 자릿수의 값들만 남기는 연산자이다.

예를들면 다음과 같다.

123 % 100 = 23

999 % 100 = 99

1100 % 100 = 0

1248 % 100 = 48

100으로 나머지 연산을 수행하면, 두 번째 자릿수까지만 살리고 나머지는 다 삭제된다.

 

그럼 (123 + 999) % 100 어떨까?

(123 + 999) % 100 = 1122 % 100 = 22

 

이번에는 (23 + 99) % 100 을 생각해보자.

(23 + 99) % 100 = 122 % 100 = 22

 

나머지 연산에서는 나머지 연산을 수행하는 값(제수) 이하의 자릿수만 의미가 있다.

그보다 큰 자릿수는 별 의미 없음을 알 수 있다. 따라서 피보나치 수도 정확히 다 기억하고 있을 필요가 없다.

우리에게 의미있는 수는 \( 2^{30} \)로 나눈 나머지 값이다.

 

6. 코드 (C++)

• Fib(1 ~ 50000) % \( 2^{30} \) 를 구한다
• (A[i]번째 피보나치 수) modulo \( 2^{B[i]} \)를 계산한다.
  A[i]번째 피보나치 수라고 표현했지만, 이 수는 \( 2^{30} \)로 나눈 나머지 값이다.

vector<int> solution(vector<int> &A, vector<int> &B) {

    int max_modulus = (1 << 30);

    vector<int> fib = {};
    fib.emplace_back(1);
    fib.emplace_back(1);
    int m = 2;
    
    while(m <= 50000)
    {
        int n = (fib[m - 1] + fib[m - 2]) % max_modulus;
        fib.emplace_back(n);
        m++;
    }

    vector<int> result = {};
    for(size_t i = 0; i < A.size(); i++)
    {
        int a = A[i];
        int n = fib[a] % (1 << B[i]);
        result.emplace_back(n);
    }

    return result;
}

 

  modulo 연산을 AND 연산으로 변경할 수도 있다. 

vector<int> solution(vector<int> &A, vector<int> &B) {

    //int max_modulus = (1 << 30);
    int max_modulus = 0x3FFFFFFF;

    vector<int> fib = {};
    fib.emplace_back(1);
    fib.emplace_back(1);
    int m = 2;
    
    while(m <= 50000)
    {
        int n = (fib[m - 1] + fib[m - 2]) & max_modulus;
        fib.emplace_back(n);
        m++;
    }
    
    vector<int> result = {};
    for(size_t i = 0; i < A.size(); i++)
    {
        int a = A[i];
        //int n = fib[a] % (1 << B[i]);
        int n = fib[a] & ((1 << B[i]) - 1);
        result.emplace_back(n);
    }

    return result;
}

 

7. 결과