[JS] 2 x n 타일링 - 이거 왜 피보나치인지 알려드림!

일단 제목부터 스포인데요.사실 이번 문제는 코드가 중요하지 않습니다.어떻게 거기까지 생각이 미치냐가 더 중요한 것 같아요.자 같이 한번 생각해보죠!

---

문제 요약

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

제한사항

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

 

정답 코드

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

정답 코드 단 7줄!

그냥 피보나치 수열 구하는 코드입니다.

왜 이렇게 나왔는지 간단히 살펴보죠

 

접근방법

일단 세로의 길이가 2로 고정이네요.

혹시 가로로 누운 (2x1) 타일이 지그재그로 배치될 수 있을까? 생각해봤지만 불가능입니다.

왜냐면 어떻게 해서든 1x1 공간이 남기 때문입니다.

 

결과적으로 한 격자를 다 채우기 위해서는 (1x2)로 넣거나 (2x1)을 상하로 배치한 (2x2)를 넣어줘야합니다.

여기에서 우리는 과감히 세로 케이스를 버려야합니다.

가로만 생각해도 충분해요.

 

가로를 n이라고 했을 때, 타일은 1 혹은 2칸짜리를 배치할 수 있는 것과 마찬가지네요.

코드로 쓴다면 이렇게 쓸 수 있겠군요.

function solution(n){
  const case1 = solution(n - 1);
  const case2 = solution(n - 2);
  //return
}

 만약 가로를 2라고 생각했을 때 1칸씩 넣는 경우와 2칸씩넣는 경우를 합해줘야합니다.

그래야 총 경우의 수를 얻을 수 있죠,

 

맞습니다. 결론적으로 저 두 값을 합해준 값이 리턴값이 되고 이건 결국 피보나치와 같은 문제라는 걸 알 수 있습니다.

 

사실 먼저 저렇게 재귀로 구현을 해봤었는데 효율성 테스트에서 걸리더라구요.

그래서 그냥 bottom-up 방식으로 변경해서 풀어봤습니다.

 

정말... 어렵네요 알고리즘이란...

그럼 이만!