백준 11726: 2 X n 타일링 - javascript(dp)

문제 출처 

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

2

예제 입력 2 복사

9

예제 출력 2 복사

55

문제 풀이 힌트 

n=1 일 때, 경우의 수는 1개

n=2 일 때, 경우의 수는 2개

n=3 일 때, 경우의 수는 3개

n=4 일 때, 경우의 수는 5개

n=5 일 때, 경우의 수는 8개 ...

 

즉, dp를 활용해서 

memo[i] = memo[i-2] + memo[i-1] 식을 구현한다 ! 

문제 풀이 코드 

const input =require('fs').readFileSync('/dev/stdin').toString().split('\n'); 
const N = Number(input.shift()); 
const memo = new Array(N+1); 0부터 N까지의 idx 배열을 만든다. 
memo[1] = 1; //n=1일 때 값 채우기 
memo[2] = 2; //n=2일 때 값 채우기 
for(let i=3; i<=N; i++){ //dp를 활용한 식 
    memo[i] = (memo[i-2] + memo[i-1]) % 10007; 
}
console.log(memo[N]);

 

문제 뽀인트 

- memo[2] 부터 채우면 안된다!! memo[1]을 물어보면 어쩔래?