백준 - 11727 2xn 타일링 2

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

11727번: 2×n 타일링 2

 

전형적인 DP 문제였다.

 

2020/08/14 - [알고리즘/백준(BOJ)] - 백준 - 11726 2xn 타일링

에 아주 약간의 조건을 추가한 문제이다. 문제 자체는 쉽다.

 

 

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> cache;

int tiling(int index) {
    if(n - 1 == index) return 1;
    if(n - 2 == index) return 3;

    int& ret = cache[index];
    if(ret != -1) return ret;

    ret = (tiling(index + 1) + tiling(index + 2) * 2) % 10007;

    return ret;
}

int main() {
    cin >> n;

    cache.assign(n, -1);

    cout << tiling(0);

    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~