본문 바로가기

코딩/알고리즘

백준) 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]);
}

 

'코딩 > 알고리즘' 카테고리의 다른 글