문제

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

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

입력

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

출력

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

로직

logic

• 2 x n 직사각형
• 2와 1의 조합으로 n이 되는 경우
• 3=> 111 와 21 일 경우
• 21은 21과 12두 경우가 있음
• 10007 로 나눈 나머지 구하기
• 규칙없나? N==1 ->1개 N==2 -> 2개, N==3 -> 3개 , N==4 -> 5개 (2+3), N==5 -> 8(5+3)
• 즉 전 값의 나머지 더해주면 됨!

풀이

{
 const N: string | null = prompt("직사각형의 가로 길이를 입력해주세요.");

if (N) {
  const n: number = parseInt(N);
  if (n >= 3 && n <= 1000) {
    const dp: Array<number> = [0, 1, 2];
    for (let i = 3; i < 1001; i++) {
      dp.push(dp[i - 2] + dp[i - 1]);
    }
    console.log(dp[n] % 10007);
  } else {
    console.log("직사각형의 가로 길이는 3이상 1000이하입니다.");
  }
} else {
  console.log("적절한 값을 입력해주세요.");
}

}
/**
 * input
   9
 * output
   55
 
 */

``