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

문제 : 2 x n 타일링

기본적인 내용

조합 (nCr)과 팩토리얼
2*1 길이의 타일을 n x 2 타일에 붙여넣는 방법 찾기

처음 생각한 방법

나는 처음 n=4일때
4개를 세로로 하는 방법 1개 ( 4C4)
4개를 |=| ,||=,=|| 형태로 3개가 나타나는 것 (3C2)
4개를 가로로 하는 방법 1개 (2C0)
조합으로 풀면 되는 줄 알았다.

조합 함수 만들기

function c(a,b){
    let up=1,down=1;
    for(let i=1;i<=b;i++,a--)
    {
      up *= a;
      down *= i;
    }
    return up/down;
  }

예를들어 c(5,2)하면 (5x4)/(2x1) 이므로 10이란 결과가 나온다.

시도한 방법

function c(a,b){
    let up=1,down=1;
    for(let i=1;i<=b;i++,a--)
    {
      up *= a;
      down *= i;
    }
    return up/down;
  }

function solution(n) {
    let answer=0;
    for(let front = n, back=n ;back>=0;front-=1,back-=2){
        answer+=c(front,back);
    }
    return answer% 1000000007;
}

이렇게 시도했으나 전부 실패했다.

실패가 뜬 이유

아마 조합 계산에서 up *= a에서 a가 웬만큼 큰 숫자인 경우 이를 반복문으로 이용하면 up 값은 js에서 수용할 수 있는 범위 이상으로 계산하기 때문에 오류가 발생한 것이라 판단된다.

다른사람의 코드 (팩토리얼)

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];
}

갈수록 증가하는것이 n=4일때 5, n=5일때 8
이는 마치 [0,1,2,3,5,8... ]과 같이 이전 값 2개의 합이 결과로 이어진다.

즉, 위와같이 n번째는 계산을하여 그때의 값을 1000000007로 나눈 나머지로 계산될 수 있다.

느낀점

nCr에만 너무 복잡하게 생각을 붙잡고있었지만 그 덕분에 nCr을 함수로 표현하는 방법은 알게 되었다.