🔗 Full Problem 1003

The following source is a C++ function that computes the Nth Fibonacci number.

CPP
int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

When you call $fibonacci(3)$, the following happens.

• $fibonacci(3)$ calls $fibonacci(2)$ and $fibonacci(1)$ (first call).
• $fibonacci(2)$ calls $fibonacci(1)$ (second call) and $fibonacci(0)$.
• The second call to $fibonacci(1)$ prints 1 and returns 1.
• $fibonacci(0)$ prints 0 and returns 0.
• $fibonacci(2)$ obtains the results of $fibonacci(1)$ and $fibonacci(0)$, and returns 1.
• The first call to $fibonacci(1)$ prints 1 and returns 1.
• $fibonacci(3)$ obtains the results of $fibonacci(2)$ and $fibonacci(1)$, and returns 2.

1 is printed twice, and 0 is printed once. Given N, write a program that computes how many times 0 and 1 are each printed when calling $fibonacci(N)$.

The first line gives the number of test cases T.
Each test case consists of one line giving N. N is a natural number less than or equal to 40, or 0.

For each test case, print the number of times 0 is printed and the number of times 1 is printed, separated by a space.

• Input

TC
3
0
1
3

• Output

TC
1 0
0 1
1 2

Something I notice while solving algorithm problems is that it's often hard to understand what the problem is even asking. Maybe it's just because I'm not that sharp.

To solve this problem, you need to understand the formula for the Fibonacci sequence.
If the Fibonacci sequence is $f()$, the formula for the nth Fibonacci number can be defined as $f(n) = f(n - 1) + f(n - 2)$.

The initial values for $n = 0, 1$ are fixed (given the nature of the formula, calculation is impossible without initial values).
$f(0) = 0$
$f(1) = 1$
These are the initial values, and meaningful computation effectively begins from $n >= 2$.

Back to the problem: given an arbitrary number N, we need to find how many times $f(0)$ and $f(1)$ are called while performing $f(N)$.
For example, suppose $N = 4$ and expand the formula as follows.
$f(4) = f(3) + f(2)$
In the above formula, $f(3)$ can be substituted with $f(2) + f(1)$, and for the same reason, $f(2)$ can also be substituted with $f(1) + f(0)$.
$f(4) = f(2) + f(1) + f(1) + f(0)$
$= f(1) + f(0) + f(1) + f(1) + f(0)$

As a result, this can be organized as $f(4) = 2(f0) + 3f(1)$.
Therefore, the algorithm for this problem should print 2 3 when $N = 4$.

First, organizing the formula so it can be seen at a glance should help solve the problem.
Laying out the Fibonacci sequence in full gives the following.

Once organized into a table, a pattern starts to become visible.

• The count of $f(1)$ printed for N is the same as $f(N)$.
• The count of $f(0)$ printed for N is the same as $f(N - 1)$.

In other words, for $N = 4$, the algorithm should print $f(3)$ and $f(4)$.

If we think about this simply, we might write code like the following.

JAVA
import java.util.Scanner;

/**
 * Baekjoon Problem 1003 algorithm class
 *
 * @author RWB
 * @since 2021.04.21 Wed 23:29:03
 */
public class Main
{
	static Integer[][] arr = new Integer[41][2];

	/**
	 * Main function
	 *
	 * @param args: [String[]] parameters
	 */
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);

		// Number of times 0 is called when N = 0
		arr[0][0] = 1;

		// Number of times 1 is called when N = 0
		arr[0][1] = 0;

		// Number of times 0 is called when N = 1
		arr[1][0] = 0;

		// Number of times 1 is called when N = 1
		arr[1][1] = 1;

		int length = scanner.nextInt();

		for (int i = 0; i < length; i++)
		{
			int n = scanner.nextInt();

			int f0 = fibonacci(n - 1);
			int f1 = fibonacci(n);

			System.out.println(f0 + " " + f1);
		}
	}

	/**
	 * Function that returns the Fibonacci value
	 *
	 * @param n: [int] index
	 *
	 * @return [int] Fibonacci value
	 */
	private static int fibonacci(int n)
	{
		// If the index is 0
		if (n == 0)
		{
			return 0;
		}

		// If the index is 1
		else if (n == 1)
		{
			return 1;
		}

		// If the index is 2 or greater (computation possible)
		else
		{
			return fibonacci(n - 1) + fibonacci(n - 2);
		}
	}
}

The above code has two major problems. First, the handling of $n = 0, 1$ is not done correctly.
$f(1) = f(0) + f(-1)$
Before N even becomes an issue, this code fails due to a runtime timeout. Why is that?

The above code performs far too many unnecessary computations. Due to the nature of the Fibonacci sequence, computing $f(N)$ inevitably computes all Fibonacci values up through N, such as $f(N - 1)$, $f(N - 2)$, and so on.
In other words, when computing $f(6)$, the Fibonacci values of $f(4)$, $f(2)$, etc. can naturally be obtained along the way.

Applying the above theory to the algorithm gives the following approach.
Suppose N is given a total of 3 times; these can be distinguished as $N_1$, $N_2$, $N_3$.

$N_2 = 8$ -> Values from $f(8)$ down to $f(0)$ can be obtained.
$N_3 = 4$ -> Values from $f(4)$ down to $f(0)$ can be obtained.

By storing the computed Fibonacci values, when $N_n > N_{n+1}$, we can simply print the already-stored value instead of performing additional computation, reducing runtime resource usage.

It seems reasonable to declare an Integer array as a member variable of the class to store the Fibonacci sequence values and use it in the algorithm's computation.

int is a primitive data type, while Integer is a wrapper class. A characteristic of wrapper classes is that they can hold a null value, so an Integer can hold a null value in addition to numbers.
The initial value of an Integer array is set to null, so any index whose value is null in the array can be determined to be an index for which the Fibonacci sequence has not yet been computed.

Fortunately, the problem's constraint for $N$ is $0 <= N <= 40$, so the array index never exceeds 41.
(Since arrays start at 0, note that it's 41 elements including 0, not just 40.)

We then add logic to the Fibonacci computation to store the value of each step in the array.
If the array's value is null, computation has not yet occurred, so the Fibonacci computation is performed and the result is stored in the array.
Conversely, if the array already holds a specific numeric value, that index has already been computed, so the value is printed directly without going through any additional computation.

JAVA
import java.util.Scanner;

/**
 * Baekjoon Problem 1003 algorithm class
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/05/21/a1003">1003 solution</a>
 * @since 2021.04.21 Wed 23:29:03
 */
public class Main
{
	static Integer[] arr = new Integer[41];
	
	/**
	 * Main function
	 *
	 * @param args: [String[]] parameters
	 */
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		
		// Fibonacci sequence initial value (N = 0)
		arr[0] = 0;
		
		// Fibonacci sequence initial value (N = 1)
		arr[1] = 1;
		
		int length = scanner.nextInt();
		
		for (int i = 0; i < length; i++)
		{
			int n = scanner.nextInt();
			
			fibonacci(n);
			
			// If n is 0
			if (n == 0)
			{
				System.out.println("1 0");
			}
			
			// If n is 1
			else if (n == 1)
			{
				System.out.println("0 1");
			}
			
			// If not an initial value
			else
			{
				System.out.println(new StringBuffer().append(arr[n - 1]).append(" ").append(arr[n]).toString());
			}
		}
		
		scanner.close();
	}
	
	/**
	 * Function that returns the Fibonacci value
	 *
	 * @param n: [int] index
	 *
	 * @return [int] Fibonacci value
	 */
	private static int fibonacci(int n)
	{
		// If the Fibonacci value at this index has not yet been computed
		if (arr[n] == null)
		{
			arr[n] = fibonacci(n - 1) + fibonacci(n - 2);
		}
		
		return arr[n];
	}
}

• Dynamic Programming