⚡2 x n 타일링

문제 설명

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

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

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

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

제한사항

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

입출력 예

n	result
4	5

result

입출력 예 설명

입출력 예 #1 다음과 같이 5가지 방법이 있다.

코드

참고

타일을 까는 바닥은 가로 길이 n, 세로 길이 2 이다.

n = 1 인 경우는 타일의 길이 1인 면이 오는 경우의 수 단 한가지이다.

n = 2 인 경우는 (1) 세로로 타일을 2개 연달아 배치 하거나, (2) 가로로 타일을 눕혀서 배치하는 경우 2가지이다.

n = 3 인 경우는 (1) 세로로 타일을 3개 연달아 배치하거나, (2) 가로로 1개 배치 + 세로로 1개 배치, (3) 세로로 1개 + 가로로 1개 배치하는 경우의 수로 3가지의 경우의 수가 존재한다.

n = 4 인 경우는 (1) 세로로 4개 연달아 배치하는 방법, (2) 가로로 1개, 세로로 2개 배치, (3) 가로로 2개, (4) 세로로 2개 배 + 가로로 1개 배치, (5) 세로 1개, 가로 1개, 세로 1개 배치하는 5가지의 경우의 수가 존재한다.

n = 5 인 경우는 마찬가지로 계산하면 총 8가지의 경우의 수가 나온다.

n 의 값이 1, 2, 3, 4, 5,... 로 증가함에 따라 그 결과값이 1, 2, 3, 5, 8... 처럼 변화하고 있다.

여기에서 반환되는 결과가 바로 피보나치 수열임을 알 수 있다.

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 이다.

따라서 다음과 같이 점화식을 구할 수 있다.

DP[n]= DP[n-2] + DP[n-1]

이 문제가 DP로 접근할 수 있는 또 다른 팁이 있다면, 문제 조건을 보면 최종 결과를 1,000,000,007로 나눈 나머지 값을 리턴해달라고 요구하고 있다. 이는 결과값이 매우 커질 수 있음을 의미하고 보통 이런 문제는 DP 와 같은 이전 값을 활용하여 누적하는 방식의 문제인 경우가 많다.

function solution(n) {
  return fibonacci(n);
}

const fibonacci = (n) => {
  const dp = new Array(n+1).fill(0);
  dp[0] = 1;  dp[1] = 1;
  for(let i = 2; i <= n; i++) {
    dp[i] = (dp[i-2] + dp[i-1]) % 1000000007;
  }
  return dp[n];
}

보통 피보나치를 DP로 구할 때 편의를 위해 1번째 값은 1, 2번째 값은 2로 미리 초기화하여 구현하곤 한다고 한다.

function solution(n) {
    let answer = [0,1] // F(0)=0, F(1)=1
    // 피보나치 F(n) = F(n-1) + F(n-2) % 1000000007
    for(let i=2; i <= n+1; i++) {
        answer[i] = (answer[i-1] + answer[i-2]) % 1000000007;
    }
    return answer.pop();
}

이렇게 구현했을 때는 테스트 케이스는 일치하지만, 효율성 테스트 4번에서 시간 초과가 난다.

function solution(n) {
    // 피보나치 F(n) = F(n-1) + F(n-2) % 1000000007
    let answer = new Array(n+1) // 배열 미리 생성
    answer[0] = 0; answer[1] = 1;
    for(let i=2; i <= n+1; i++) {
        answer[i] = (answer[i-1] + answer[i-2]) % 1000000007;
    }
    return answer.pop();
}

그래서 배열을 미리 생성하고 할당하는 방식을 했더니 효율성 테스트 4번은 통과했으나 이번엔 3번에서 시간 초과가 났다.

function solution(n) {
    // 피보나치 F(n) = F(n-1) + F(n-2) % 1000000007
    let answer = new Array(n+1).fill(0); // 배열 생성 & 채워주기
    answer[0] = 0; answer[1] = 1;
    for(let i=2; i <= n+1; i++) {
        answer[i] = (answer[i-1] + answer[i-2]) % 1000000007;
    }
    return answer.pop();
}

그래서 다시 배열을 생성하고 채워준 형태로 할당해주었더니 통과되었다..!

다른 풀이

function solution(n) {
  const arr = [0, 1, 2];
  for (let i = 3; i <= n; i++) {
    arr[i] = (arr[i - 2] + arr[i - 1]) % 1000000007;
  }
  return arr[n];
}

그래서 코드를 깔끔하게 작성한 다른 사람의 코드를 보면 위와 같이 작성할 수 있다. 너무 어렵다🥲

Previous124 나라의 숫자 Next3 x n 타일링

Last updated 1 year ago