11726번 2×n 타일링 문제를 풀어보았다.

11726 2×n 타일링

 

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

11726번: 2×n 타일링

 

처음에는 굉장히 어려워보였다.

그도 그럴게 문제를 제대로 안읽어서 2×n칸을 2×1, 1×2 타일로 채워넣는 문제를 n×n칸을 채워넣는 문제라고 생각했기 때문이다.(괜찮다 금방 눈치채서 시간을 낭비하는 일은 없었다.)

나는 이 문제를 당연히 DP문제라고 생각했다.

경우의 수를 구하는 문제이기 때문에 DP로 어떻게 때려넣을지를 고민하기 전에 메모장에 대충 n에 대한 경우의 수를 구해보기 시작했다.

그러고 보니까 이게 1,2,3,5,8,13...잠깐, 이거 피보나치다.

복잡할거라고 생각하고 있었는데, 의외로 간단하게 풀렸다.

 

#include <stdio.h>
int main()
{
    int n,i,D[1001];
    scanf("%d",&n);
    D[1]=1;
    D[2]=2;
    for(i=3;i<=n;i++) D[i]=(D[i-1]+D[i-2])%10007;
    printf("%d",D[n]);
}