백준) 1904 - 01타일 JS

📌 문제 링크

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

---

📌 문제 탐색하기

• 타일이 00, 1이 있다 이때 만들 수 있는 모든 가짓수를 세서 15746으로 나눈 나머지를 출력해라

시간복잡도

• O(n)

알고리즘 선택

• DP

---

📌 코드 설계하기

1. 문제의 `input`을 숫자로 변환합니다.
2. `arr`에 값을 넣어 초기화해줍니다.
   1. 문제 참조) N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다.
3. `input`이 2보다 같거나 작다면 `arr[input]`의 값을 출력합니다.
4. 그렇지 않다면 `arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;`으로 `arr`에 값을 할당합니다.
5. `arr[input]`으로 가짓수를 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

1회차

• 정말 바보같이 `arr[i] = arr[i - 1] + arr[i - 2] % 15746;` 이렇게 작성했다.. 왜 시작하자마자 틀리게 나오는거지? 했다가 급하게 괄호를 넣게 되었다...🤦🏻‍♀️

---

📌 기억해야 할 부분

• JavaScript의 배열은 정적 크기가 아니라 동적 크기
• `arr[i] = 값;` 코드를 실행하면, i번째 인덱스가 아직 존재하지 않더라도, 자동으로 배열 크기를 확장하여 i번째 위치에 값을 저장
• 예를 들어, i = 3일 때 `arr[3] = arr[2] + arr[1]`을 할당하면 arr 배열이 [0, 1, 2, 3]처럼 확장됩니다.

---

📌 정답 코드

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

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input1.txt";
const input = Number(fs.readFileSync(filePath));
const arr = [0, 1, 2];

if (input <= 2) {
  console.log(arr[input]);
} else {
  for (let i = 3; i <= input; i++) {
    arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;
    console.log(arr);
  }
  console.log(arr[input]);
}