백준) 2193 - 이친수 JS

📌 문제 링크

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

---

📌 문제 탐색하기

• N자리 이친수의 개수를 출력한다. 이친수의 성질은 아래와 같다.
  • 이친수는 0으로 시작하지 않는다. 
  • 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

시간복잡도

• O(n)

알고리즘 선택

• DP

---

📌 코드 설계하기

1. 문제의 input을 숫자로 변환합니다.
2. `DP` 배열을 선언하고 `input + 1`개의 빈 배열을 만듭니다.
3. 배열의 인덱스를 일치시키기 위해 `dp[0]`을 선언합니다.
4. `dp[1]`은 1자리 이친수의 경우로, 1로 끝나는 경우 `dp[1][1]`는 1가지만 있습니다.
5. 반복문을 통해 이친수 개수를 계산합니다.
   1. i자리에서 0으로 끝나는 이친수의 개수는 (i-1자리의 0으로 끝나는 경우 + i-1자리의 1로 끝나는 경우) 입니다.
   2. i자리에서 1로 끝나는 이친수의 개수는 i-1자리에서 0으로 끝나는 경우에 1을 붙인 것입니다.
6. 마지막 자리 수에서 0과 1로 끝나는 경우를 합하여 NNN자리 이친수의 개수를 구합니다.

---

📌 정답 코드

//https://www.acmicpc.net/problem/2193
export {};

const fs = require('fs');
const filePath =
  process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input1.txt';
const input = Number(fs.readFileSync(filePath).toString().trim());

const dp = new Array(input + 1);
dp[0] = [0, 0];
dp[1] = [0, 1];

for (let i = 2; i <= input; i++) {
  dp[i] = [];
  dp[i][0] = BigInt(dp[i - 1][0] + dp[i - 1][1]);
  dp[i][1] = BigInt(dp[i - 1][0]);
}

console.log(BigInt(dp[input][0] + dp[input][1]).toString());