[알고리즘 / 백준] 1003 - 피보나치 함수

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

문제는 위와 같으며, 각 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해 출력하는 문제입니다.

 

이 문제는 작은 수부터 차례로 살펴보면 다음과 같은 규칙을 찾을 수 있습니다.

n 번째 수의 0이 출력되는 횟수는 (n - 1 번째 수의 0이 출력되는 횟수)와 (n - 2 번째 수의 0이 출력되는 횟수)를 더한 값입니다. 1이 출력되는 경우도 마찬가지 규칙을 가져 각각 피보나치 수열을 이룬다는 것을 확인할 수 있습니다. 

 

따라서 주어지는 수가 40 이하인 자연수 또는 0이기 때문에 각 수의 0이 출력되는 횟수와 1이 출력되는 횟수를 담는 이차원 배열을 만들고 배열을 돌면서 모든 값을 미리 확인한 뒤 입력 값이 주어지면 그 값에 해당하는 인덱스의 값을 출력하는 방식으로 해결할 수 있습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

result = [[0, 0] for _ in range(41)]
for i in range(len(result)):
    if i == 0:
        result[i] = [1, 0]
    elif i == 1:
        result[i] = [0, 1]
    else:
        result[i] = [result[i - 1][0] + result[i - 2][0], result[i - 1][1] + result[i - 2][1]]

test_case = int(stdin.readline())
for _ in range(test_case):
    n = int(stdin.readline())
    print(result[n][0], result[n][1])

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[][] result = new int[41][2];
        result[0][0] = 1;
        result[1][1] = 1;
        for (int i = 2; i < result.length; i++) {
            result[i][0] = result[i - 1][0] + result[i - 2][0];
            result[i][1] = result[i - 1][1] + result[i - 2][1];
        }

        int testCase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testCase; i++) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(result[n][0] + " " + result[n][1]);
        }
    }
}