[백준] 11726 - 2 x n 타일링

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

11726번: 2×n 타일링

 

처음에 머리로만 풀려다 확률론까지 생각했다 난이도 보고 DP 문제일거라 직감했습니다. 그리고 아래와 같이 그리면서 규칙을 찾았고 해결했습니다. DP 문제는 직접 세거나 그림으로 도식화하기 전에는 DP 인지 판별이 어려워 많은 연습이 필요할 것 같습니다.

 

 

#include <iostream>
#define MAX 1001
using namespace std;

int dp[MAX];
int n;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    dp[1] = 1;
    dp[2] = 2;

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

    cout << dp[n] << "\n";
    return 0;
}