Lv.4 3 x n 타일링

문제 설명

자료 구조

• arr
  • 타입 : 배열
  • 저장 데이터 : 수열을 만들기 위한 변수
• i
  • 타입 : 정수
  • 저장 데이터 : arr 배열에 사용할 인덱스

풀이 과정

• 2 x n 타일링과 동일한 원리다.
• 단, n이 홀수일 땐 타일을 채울 방법이 없으므로 0을 return한다.
• 구현할 때 수가 너무 커지므로 BigInt로 처리했다.

가로가 n인 바닥을 채우는 경우의 수:= f(n)
예) f(2) = 3 , f(4) = 11...

f(6) = f(4)에서 두 칸을 채운다 + f(2)에서 네 칸을 채운다
f(8) = f(6)에서 두 칸을 채운다 + f(4)에서 네 칸을 채운다 + f(2)에서 여섯 칸을 채운다
f(10) = f(8)에서 두 칸 + f(6)에서 네 칸 + f(4)에서 여섯 칸 + f(2)에서 여덟 칸...

※ 2 x n 타일링 문제에서는 두 칸을 채우는 방법, 한 칸을 채우는 방법이 유일했다.
하지만 이번 문제에선 두 칸을 채우는 방법이 세 가지, m > 2일 때 2m칸을 채우는 방법은 두 가지다.

-> f(2n) = 3f(2(n-1)) + 2f(2(n-2)) + ... + 2*f(2)이다.

홀수는 빼고 짝수만 계산하면 절반이므로 n = n / 2로 나눠서 일반식을 다시 전개.

f(n) = 3f(n-1) + 2f(n-2) + 2f(n-3) + 2f(n-4) ... + 2f(2)

아이디어를 하나 추가하면, f(n-1)을 같이 전개해서 둘을 비교해보자.

f(n)   = 3f(n-1) + 2f(n-2) + 2f(n-3) + 2f(n-4) ... + 2f(2)
f(n-1) =           3f(n-2) + 2f(n-3) + 2f(n-4) ... + 2f(2)  

두 식을 빼면 매우 간단해진다.

f(n) - f(n-1) = 3f(n-1) - f(n-2)
=> f(n) = 4f(n-1) - f(n-2)

∴ f(n) = 4 * f(n-1) - f(n-2)

e.t.c) 2/2 + 2/3 + 2/(311) + 2/(1141) + 2/(41153) + 2/(153571) + ... = √3

코드 구현(JavaScript)

function solution(n) {
	let arr = [3n, 11n];
  
	for (let i = 2; i < n / 2; i++) {
      arr.push(4n * arr[i - 1] - arr[i - 2]);
    }
  
	return Number(arr[arr.length - 1] % 1000000007n);
}

출처: 프로그래머스