[프로그래머스][LEVEL3] 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

 

# 문제 풀이

피보나치 계열 문제이다. 다만 효율성 테스트 케이스가 과하게 커서 재귀 함수로 짤 경우 콜 스택 터짐에 의한 런타임 에러를 보게 된다. 반복문으로 변경해줬다. 1과 2부터 시작하는 피보나치수열을 구현해주면 되는 문제이고, 문제 지문 읽자마자 규칙성이 보이더라 앞으로 해당 유형과 비슷한 문제들은 모두 피보나치를 참고해서 구현해주면 될 거 같다. 이래서 많이 풀어봐야 한다는 것 같다.

 

# 솔루션 플로우

1. 입력 받은 N이 1일 경우 1을 반환해준다.

2. 피보나치 1번째 2번째 수인 1과 2를 a, b로 선언해준다.

3. 입력 받은 n - 3 만큼 반복하며 a 와 b를 더한 값에서 1000000007 을 나눈 나머지(b)와 a(이전 b)를 계속 더해준다.

4. 반복이 끝난후 구해진 b를 반환한다.

1. 반복문을 활용한 풀이

function solution(n) {
    if(n === 1) return 1;
    let a = 1;
    let b = 2;
    for(let int = 2; int < n; int++){
        const state = b;
        b = (a + b) % 1000000007;
        a = state;
    }

    return b;
}