오늘을 배우고 내일을 개발하다

문제 링크 : https://www.acmicpc.net/problem/11726

[문제]

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

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

[입력]

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

[출력]

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

[알고리즘 분류]

• 다이나믹 프로그래밍

[해설]

이 문제는 다이나믹 프로그래밍으로 분류되어 문제에서 규칙성을 찾아 해결해야하는 문제이다.
문제에 필요한 규칙을 찾는 방법은 다양하겠지만, 필자의 경우에는 1×2, 2×1 타일들이 들어갈 수 있는 경우의 수들을 직접 그려보고 2×3 --> 3, 2×4 --> 5, 2×5 --> 8으로 피보나치 수열 규칙성이 적용되는 것을 확인하여 이를 해결할 수 있었다.

[정답 코드]

#include<ios>
int n,d[1001]={1,1};

int main(){
  scanf("%d",&n);
  for(int i=2;i<=n;i++) d[i]=(d[i-1]+d[i-2])%10007;
  printf("%d\n",d[n]);
}

[결과]