백준 11727 2xn 타일링 2

문제

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

풀이전략

1. 이전 타일링 문제와 풀이 방법은 거의 같다. 단순히 하나의 케이스만 추가하는 것이다.
   tiling(n+1) = tiling(n) + 2*tiling(n-1)

코드

#include<bits/stdc++.h>

using namespace std;

#define mine

int N;
int dp[1001];
const int MOD = 10007;
int tiling(int n){
    if(n == 1) return 1;
    if(n == 2) return 3;
    int& ret = dp[n];
    if(ret != -1) return ret;
    return ret = (tiling(n-1) + 2*tiling(n-2))%MOD;
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    memset(dp, -1, sizeof(dp));

    cin >> N;
    cout <<tiling(N)<<endl;

    return 0;
}

소감

더해주고 나머지를 구하는것 잊지말아야한다. 또한 만약 빼고 나머지를 구하는 경우 (A-B)%MOD를 구할때는 음수가 나올수도 있으므로 (A-B + MOD) %MOD 로 계산해주어야 한다.