[자바스크립트] 2 x n 타일링

Lv. 2. 2 x n 타일링

문제

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

 

제한사항

• 가로의 길이 n은 60,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

 

 

입출력 예

 

 

자료구조

① 정수: prev, curr

 

 

알고리즘

① 초기 값 설정:

 

• `prev`는 피보나치 수열의 첫 번째 값인 $F(1)$을 의미하며, `prev = 1`로 초기화됩니다.
• `curr`는 피보나치 수열의 두 번째 값인 $F(2)$를 의미하며, `curr = 2`로 초기화됩니다.
• 특수 케이스 처리:
  • `n`이 1일 경우, `prev` 값을 반환합니다.
  • `n`이 2일 경우, `curr` 값을 반환합니다.

② 반복문을 통한 수열 계산:

• 피보나치 수열의 각 항을 계산하면서 `MOD`로 나눈 결과를 사용하여 `prev`와 `curr` 값을 업데이트합니다.
• 반복 과정:
  • `i`가 3부터 시작하여 n까지 반복하면서 수열의 값을 계산합니다.
  • `next`는 `prev`와 curr의 합을 계산한 다음 `MOD`로 나눈 값을 저장합니다.
  • `prev`는 `curr` 값으로, `curr`는 `next` 값으로 업데이트됩니다. 이를 통해 다음 반복에서 사용할 준비를 합니다.

 

 

소스 코드 

function solution(n) {
  const MOD = 1000000007;
  let prev = 1;
  let curr = 2;

  if (n === 1) return prev;
  if (n === 2) return curr;

  for (let i = 3; i <= n; i++) {
    const next = (prev + curr) % MOD;
    prev = curr;
    curr = next;
  }

  return curr;
}

• 태뷸레이션 (Tabulation):
  • 상향식(Bottom-up)은 반복문을 사용합니다.

 

• 시간 복잡도: 이 알고리즘은 $O(n)$의 시간 복잡도를 가집니다. `n`이 커질수록 반복 횟수가 증가하지만, 계산은 단순한 덧셈과 나머지 연산으로 이루어져 있어 매우 효율적입니다.
• 공간 복잡도: 두 개의 변수(`prev`, `curr`)만을 사용하므로, 공간 복잡도는 $O(1)$입니다. 이는 메모리 효율성을 극대화한 방법입니다.

 

 

 

 

✔ 출처

https://school.programmers.co.kr/learn/courses/30/lessons/12900