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

11727 2×n 타일링 2

 

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

11727번: 2×n 타일링 2

 

저번의 타일링 문제의 리벤지 문제다.

와, 이번에는 무려 2×2 타일이 있다.

그리고 범위를 아득히 뚫고 나가는 문제로 인해 결과 값을 10007로 나눈 나머지 값을 출력하도록 한다.

따라서 경우의 수도 기하학적으로 늘어나게 되는데, 대충 그려가면서 경우의 수를 구해보았다.

1 3 11 21 43 ... 의 수열을 얻을 수 있었는데 정말 이 적은 수를 가지고 점화식을 구하는 데 많이 힘들었다.

그도 그럴게 직접 경우마다 그려가면서 구했는데 6번째가 43개라는 값을 얻을 수 있었다는건 내가 직접 그려서 구한 것이기 때문이다.

어쨌든 나는 이 적은 수들을 가지고 한가지 점화식을 세울 수 있었다.

f(0)=1

f(1)=3

f(n)=(f(n-1)+f(n-2)*2)%10007

점화식을 구하기가 어려웠지 문제 자체는 쉬운 DP문제였다.

어, 아닌가 재귀 응용이 더 맞으려나.(뭐든간 풀었으면 장땡이지 뭐)

 

#include <stdio.h>
#include <stdlib.h>
long long* arr;
long long f(long long x) {
    if(arr[x]) return arr[x];
    return arr[x]=(f(x-1)+f(x-2)*2)%10007;
}
int main()
{
    long long n;
    scanf("%lld", &n);
    arr=(long long*)calloc(1,sizeof(long long)*n);
    arr[0]=1;
    arr[1]=3;
    printf("%lld",f(n-1));
}