BaekJoon_1003(피보나치 함수)

문제

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

문제풀이

0,1 이 각각 몇번씩 호출되는지 2가지의 경우로 나누어 생각하여 풀었다.

N = 0일 때는 0이 1번, 1이 0번

N = 1일 때는 0이 0번, 1이 1번

N = 2일 때는 0이 1번, 1이 1번

N = 3일 때는 0이 1번, 1이 2번

N = 4일 때는 0이 2번, 1이 3번

N = 5일 때는 0이 3번, 1이 5번

 

0이 반복되는 횟수는 1,0,1,1,2,3...

1이 반복되는 횟수는 0,1,1,2,3,5...

 

각각 0,1이 피보나치 수열의 형태를 보이고 있다.

이를 점화식으로 표현하면 아래와 같이 나타난다.

0의 갯수 => F(n) = F(n-1) + F(n-2)

1의 갯수 => F(n) = F(n-1) + F(n-2)

 

0의 초기값은 dp[0] = 1, dp[1] = 0

1의 초기값은 dp[0] = 0, dp[1] = 1

 

코드

const answer = (arr) => {

    const inputArr = [];

    const parseN = Number(arr[0]);

    for (let index = 1; index <= parseN; index++) {
        inputArr.push(Number(arr[index]))
    };

    for (let index = 0; index < inputArr.length; index++) {

        // 1. 0 호출되는 리스트 만들기
        const zeroArr = Array.from({ length: inputArr[index] + 1 }, () => 0);

        // 1-2. 초기값 설정
        zeroArr[0] = 1;
        zeroArr[1] = 0;

        // 1-3. 점화식 적용
        for (let i = 2; i < zeroArr.length; i++) {
            zeroArr[i] = zeroArr[i - 1] + zeroArr[i - 2]
        }

        // 2. 1 호출되는 리스트 만들기
        const oneArr = Array.from({ length: inputArr[index]  + 1}, () => 0);

        // 2-1. 초기값 설정
        oneArr[0] = 0;
        oneArr[1] = 1;

        // 2-2. 점화식 적용
        for (let j = 2; j < oneArr.length; j++) {
            oneArr[j] = oneArr[j - 1] + oneArr[j - 2]
        }

        // 3. 화면 출력
        console.log(`${zeroArr[inputArr[index]]} ${oneArr[inputArr[index]]}`);
    }


}


const input = [];
require("readline")
    .createInterface(process.stdin, process.stdout)
    .on("line", (line) => {
        input.push(line);
    })
    .on("close", () => {
        answer(input);
        process.exit();
    });

 

소스코드는 깃헙에서도 확인 가능합니다 :)

https://github.com/duduchi/Algorithm/tree/main/Dynamic

GitHub - duduchi/Algorithm: 알고리즘 이론 및 구현 소스 정리 프로젝트 입니다.