[JavaScript/DP] 백준 실버 3 : 1003 - 피보나치 함수

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

1003번: 피보나치 함수

---

📌 작성한 코드 

// 1003
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const T = Number(input.shift());

for (let i = 0; i < T; i++) {
    const N = Number(input[i]);

    // const dp = new Array(N + 1);
    // dp[0] = 0;
    // dp[1] = 1;

    const count = Array.from({ length: N + 2 }, () => new Array(2).fill(0));
    count[0][0] = 1;
    count[0][1] = 0;
    count[1][0] = 0;
    count[1][1] = 1;

    for (let j = 2; j <= N; j++) {
        // dp[i] = dp[i - 1] + dp[i - 2];
        count[j][0] = count[j - 1][0] + count[j - 2][0];
        count[j][1] = count[j - 1][1] + count[j - 2][1];
    }

    console.log(count[N].join(" "));
}

📌 풀이

피보나치 수를 구하는 dp 함수에서 0과 1의 개수를 저장하는 dp로 바꾸면 되는 문제이다. 

 

재귀 함수로 피보나치 수를 구하게 되면 같은 연산이 너무 많이 반복되어서 시간이 많이 소요된다. 그래서 같은 연산을 다시 하지 않고 이전에 한 연산을 저장했다가 사용하는 dp를 사용해서 구현한다. 그러나 이번 문제에서 구하고 싶은 것은 피보나치 수가 아니라 피보나치 수를 구하는 재귀 함수에서 0과 1이 나올 때의 개수이다. 어떻게 구현해야 할지 막막할 수 있지만 dp를 사용해서 구현하면 매우 간단하게 구할 수 있다.  피보나치 수를 구한 것 처럼 이전에 나온 0과 1의 개수를 가져와서 더해주면 된다.

 

count 이차원 배열을 선언해서, 해당 단계까지 오는데 나온 0과 1을 저장해주는 것이다.

- 정의 : count[i] : 숫자 i까지 오는데 출력된 0과 1의 개수를 저장

- 점화식 : `count[i][0] = count[i - 1][0] + count[i - 2][0]` , `count[i][1] = count[i - 1][1] + count[i - 2][1]`

const count = Array.from({ length: N + 2 }, () => new Array(2).fill(0));
count[0][0] = 1; // 초기화
count[0][1] = 0;
count[1][0] = 0;
count[1][1] = 1; 

for (let j = 2; j <= N; j++) {
    // dp[i] = dp[i - 1] + dp[i - 2]; // 피보나치 수를 구하는 dp 함수
    count[j][0] = count[j - 1][0] + count[j - 2][0]; // 0의 개수 구하기 
    count[j][1] = count[j - 1][1] + count[j - 2][1]; // 1의 개수 구하기
}

 

✅ 성공