[프로그래머스] 2 x n 타일링 - JS

연습문제 - 2 x n 타일링

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

 

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

- 타일을 가로로 배치 하는 경우
- 타일을 세로로 배치 하는 경우
예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

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

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

 

입출력 예
n result
4 5

 

입출력 예 #1

다음과 같이 5가지 방법이 있다.

 

 

내 풀이 1 (실패)

function solution(n) {
    const dp = Array(n);
    dp[0] = 1;
    dp[1] = 2;

    if (n < 2) return dp[n]; // 입력이 2 미만이면, dp[0] 또는 dp[1] 반환
    
    for (let i = 2; i < n; i++) {
        // 현재 단계의 값 = (직전 값 + 두 단계 전 값) % 1000000007
        // 매우 큰 숫자를 다룰 때 초과 방지
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
    }
    return dp[n - 1];
}

 

일단 이 풀이는 95점 이었는데
두 이전 값의 합을 구하고, 결과를 1000000007로 나눈 나머지를 저장하는 방식이었다.

배열을 사용해서 풀었는데 효율성 테스트를 통과하지 못했다. ㅠㅠ

이 풀이의 시간복잡도는 O(n)이고, 공간 복잡도도 O(n)이다.

 

 

내 풀이 2 (실패?)

function solution(n) {
    var answer = 0;
    let a = 2, b = 1; // a: 현재 단계의 값, b: 이전 단계의 값

    if (n === 1) return b; // n = 1일 경우 결과는 b(= 1)
    if (n === 2) return a; // n = 2일 경우 결과는 a(= 2)

    for (let i = 2; i < n; i++) {
        // 현재 단계의 값 = (이전 단계의 값 + 그 이전 단계의 값) % 1000000007
        answer = (a + b) % 1000000007;

        // 다음 단계 계산을 위해 이전 값들을 업데이트
        b = a;      // b는 현재 단계의 값으로 갱신
        a = answer; // a는 현재 계산된 결과로 갱신
    }
    return answer;
}

 

위 풀이를 실패하고 변수 기반 dp로 바꿨다.

근데도 효율성 테스트를 통과하지 못함.(왜???)

끝나고 검색해보니 이 풀이로 통과한 사람들은 많았다.

코치님도 이 풀이로 통과하셨다(...)

이 풀이의 시간복잡도는 O(n)이고, 공간 복잡도는 O(1)이다.

 

내 풀이 3 (성공)

function solution(n) {
    let answer = 0;
    let c = 2, b = 1;
    let mod = 1000000007;
    for(let i = 2; i < n; i++){
        answer = (c + b) % mod;
        b = c;
        c = answer;
    }
    return answer;
}

 

사실 위 풀이와 다른 점은... 없다.

코치님 조언에 따라 answer을 var에서 let으로 바꿔주었고

100000007을 mod로 선언했을 뿐...

통과했다.

본질적인 코드는 그냥 두번째 코드랑 같은데 왜? 이건 통과 되었는지 의문.

어쨌든 해결~..

 

---

 

근데 이 문제는 참 애매한 것 같다.

질문 하기 보니까 뭔가 문제가 있는 듯??