[JS] 2 x n 타일링

 

 

난이도: Lv. 2

정답률: 54%

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

프로그래머스

 

 

알고리즘

1. n만큼의 길이를 가지는 배열을 1로 초기화한다..

2. n번째 피보나치수열을 구하기 위해 i 번째 피보나치 수를 계산하고 값을 1000000007로 나눈 나머지를 1. 에서 생성한 배열에 저장한다.

3. n번째 피보나치 수를 1000000007로 나눈 나머지를 리턴한다.

 

 

코드

function solution(n) {
    const fibo = Array.from({ length: n + 1 }, () => 1);

    for (let i = 2; i <= n; i++) {
        fibo[i] = (fibo[i - 2] + fibo[i - 1]) % 1000000007;
    }

    return fibo[n];
}

 

 

주저리

시간 초과날 게 확실하지만 그래도 혹시나 해서 dfs로 풀어봤는데 역시나 시간초과가 났다. 1과 2로 n을 만들 수 있는 경우의 수를 순서를 고려하여 구하는 문제임을 인지했으나 Combination 연산을 컴퓨터가 감당할 수 없음이 너무나도 확실해서 어떻게 풀지 고민하는데 문득 이런 문제 풀어본 적 있다는 생각이 들었다. 근데 어떻게 풀었었는지는 기억이 전혀 안 나서 노트에 이거 저거 끄적이다가 n에 따른 정답을 적어보니 피보나치수열임이 보였다. 그 문제도 피보나치수열로 풀었던 게 기억이 났다. 그래서 피보나치로 풀었는데 효율성이 다 틀려서 뭐가 문젠가 했는데 배열에 push 하는 형식이 아니라 배열을 먼저 초기화하고 인덱싱 해서 값을 저장하는 형태로 풀어야 했던 것이다. 배열을 항상 초기화하고 푸는 습관을 들여야겠다.