보드의 칸 채우기 문제

입력: number 타입 자연수(1이상)
출력: number 타입 리턴(경우의 수)

조건: 세로길이 2, 가로길이 n인 2xn 크기의 보드가 존재

2x1 크기의 사각형으로 이 보드를 채우는 모든 경우의 수를 리턴해라

 

주의사항:

사각형은 가로, 세로 어느 방향으로 놓아도 됨
각각의 사각형은 모두 같다고 생각(중복허용x)

 

사실상 생각해보면 피보나치 수열과 같은 문제임

아래 코드를 살펴보자

let fillingSquare = function (n) {

// 1 2 3 5 8 13 21 34 55 89(10) 144(11) 233(12) 377(13) 610(14) 987(15) 
//<- 항상 앞의 두 수의 합이 그다음의 수임
// 즉 피보나치 수열과 비슷한듯하다?

// 재귀 함수로 생각해보자(재귀적 동적 계획법 이용)

// 결과값을 담고 참조할 배열 생성
let temp=[0,1,2]; // n은 1부터 시작하므로 인덱스 번호1이 1에 매칭이 되게 더미데이터용 0 삽입
// 해당 배열 안에 찾고자 하는 값이 없으면 새로 만들어서 배열에 넣어주기
//(메모하는 캐시 배열을 만들어서 값을 채우는 개념)

let squareCheck = function(num) {
if(temp[num] !==undefined){ // undefined가 아니면 즉, 값이 존재하는 경우
return temp[num]; // 그 전에 저장한 값을 리턴
}
// 그렇지 않은 경우(값이 존재하지 않는 경우)
temp[num]= squareCheck(num-2)+squareCheck(num-1); 
// 값이 존재하지 않으므로 재귀 함수를 통해 값을 생성
return temp[num];
};

return fillingSquare(n);

};

// 입출력 예시

let output = fillingSquare(2);
console.log(output); // --> 2

output = fillingSquare(4);
console.log(output); // --> 5
/* 
2 x 4 보드에 사각형을 놓는 방법은 5가지
각 사각형을 a, b, c, d로 구분

2 | a b c d
1 | a b c d 
------------

2 | a a c c
1 | b b d d 
------------

2 | a b c c
1 | a b d d 
------------

2 | a a c d
1 | b b c d 
------------

2 | a b b d
1 | a c c d 
------------
*/