[백준 알고리즘] Node.js 1003. 피보나치 함수

1. 문제

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

1003번: 피보나치 함수

 

2. 풀이

1) 처음엔 그냥 문제에 주어진 대로 문제풀이를 진행했다. 아래는 그 코드이다.

const [T, ...inputs] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(v => +v);

// answer array에 0이 되는 회수와 1이 되는 회수를 만듬.
const answer = Array.from({length : T}, () => [0,0]);


// C++로 만든 함수를 JS로 바꿈. 이후 0과 1이 될 때마다 해당 array의 값 증가.
const fib = (idx, n) => {
    if(n === 0){
        answer[idx][0]++;
        return 0;
    } else if(n === 1){
        answer[idx][1]++;
        return 1;
    } else {
        return fib(idx, n-1) + fib(idx, n-2);
    }
}

// 테스트케이스만큼 반복.
for(let i = 0; i < T; i++){
    let num = inputs[i];
    fib(i, num);
}

// 결과 출력.
let result = "";
answer.forEach(item => {
    result += `${item.join(" ")}\n`;
})

console.log(result)

- 시간 초과났다. 이번 문제는 DP 를 이용해야하는 문제였기 때문이다. 혹시나 했는데 역시 안된다 ^^;;;;

 

2) 이번엔 DP를 이용해보자. 

- 이전에 피보나치 관련 문제를 푼 기억이 났다. 관련 문제는 백준 24416번 문제!!

- 0일때 0을 출력하는 횟수와 1을 출력하는 횟수, 1일때 0을 출력하는 횟수와 1을 출력하는 횟수를 기본으로 둔다.

- 만약 2라면 0과 1을 1번씩 출력한다. 3이라면 0을 1번, 1을 2번 출력.

- 이를 통해 알 수 있는 사실은

fibonacci[i] = [
	fibonacci[i-1][0] + fibonacci[i-2][0], // 0이 등장하는 횟수
    fibonacci[i-1][1] + fibonacci[i-2][1] // 1이 등장하는 횟수
]

로 표현이 가능하다!!

 

const [T, ...inputs] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(v => +v);


for(let i = 0; i < T; i++){
  const num = inputs[i];

  const fibo = [[1,0], [0,1]];

  for(let j = 2; j <= num; j++){
    fibo[j] = [
      fibo[j-1][0] + fibo[j-2][0],
      fibo[j-1][1] + fibo[j-2][1]
    ];
  }

  console.log(fibo[num].join(" "));
}

 

3. 정리

- DP 어렵다. DP의 핵심은 "메모이제이션" 이라고 한다~