백준 - 11726 2xn 타일링

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

11726번: 2×n 타일링

전형적인 DP 문제였다. 그리고 타일링 문제는 계단 오르기 문제랑 같이 DP에서 유명한 유형이다.

 

구현만 하면 되는 문제였다.

 

 

 

#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 2;

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

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

    return ret;
}

int main() {
    cin >> n;

    cache.assign(n, -1);

    cout << tiling(0);

    return 0;
}

 

 

개발 환경 : vscode

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