#11727 2xn 타일링 2

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

11727번: 2×n 타일링 2

실버 3의 문제이다. dp문제답게 실버3치고는 어려웠던, 하지만 그나마 쉽게 풀수 있었던 문제이다.

#include <iostream>
#include <algorithm>
#define mod 10007
using namespace std;

int n;
long long dp[1001];

int main()
{
  //freopen("input.txt","r",stdin);
  cin>>n;
  dp[1]=1;
  dp[2]=3;

  for(int i=3;i<=n;i++){
    dp[i]=(dp[i-1]+dp[i-2]+dp[i-2])%mod;
  }

  cout<<dp[n]%mod;
}

코드는 굉장히 단순하다. 일단 문제에서 n의 최대값으로 1000을 주었고 이는 굉장히 큰 수가 될것임을 알아차리고 dp배열은 long long 형으로 설정해주었다.

 

이문제는 마지막 타일을 두지않을때 어떻게 되는지를 중심으로 점화식을 구성하면 된다.

dp[n] 을 2xn 타일을 채우는 방법의 수라고 하였을때, 마지막 타일을 두지않는 방법 3가지를 따져보면 된다.

첫째로, 1x2타일을 두지 않았을때 타일을 둔 부분은 dp[n-2]가 된다.

둘째로, 2x1타일을 두지 않았을때 타일을 둔 부분은 dp[n-1]가 된다.

마지막으로, 2x2타일을 두지 않았을때 타일을 둔 부분은 dp[n-2] 가 된다.

 

결론적으로 dp[n] = dp[n-1] + dp[n-2] + dp[n-2] 가 되는 것이다.

또, 계산시 나오는 수가 굉장히 클 수 있기때문에 계산을 할때마다 mod로 나누어주어 dp배열에 넣었다!