BOJ 11726 2*N 타일링

BOJ : https://www.acmicpc.net/problem/11726

GitHub : https://github.com/junho0956/Algorithm/blob/master/11726/11726/%EC%86%8C%EC%8A%A41.cpp

 

2*N 타일링을 처음 풀었을 때는

이걸 어떻게 하나 했는데 손으로 작성해보니 피보나치와 같은 값을 가진다는 것을 알고 해결했었다.

그냥 규칙찾는 문제인줄 알았는데 다른 타일링 문제를 풀면서

타일링 문제를 제대로 푸는 방법을 알게 되었고

타일링문제의 기본인 2*N 타일링을 다시 풀어보았다.

여러 타일링 문제에 접목시킬 수 있는 가장 기본기 인 것 같다.

 

#include <iostream>
using namespace std;
#define MOD 10007
int N;
int dp[1001];
 
int solve(int len) {
// 0 미만이라면 가질 수 있는 값이 없다. ex) 1 계산시 알게됨
    if (len < 0) return 0;
// 0 과 1 이라면 1이라는 값을 가질 수 있다.
    if (len <= 0) return 1;
 
    if (dp[len]) return dp[len];
 
// 가로로 1칸을 준 경우 + 세로로 2칸을 준 경우
    dp[len] = (solve(len - 1) + solve(len - 2)) % MOD;
    return dp[len];
}
 
int main() {
    ios::sync_with_stdio(false);
 
    cin >> N;
    cout << solve(N);
    return 0;
}