[백준(BOJ)] 11726번: 2×n 타일링 (Dynamic Programming, C++)

💻 C++ 제출코드

---

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    
    scanf("%d", &n);
    
    vector<int> DP(n);
    DP[0] = 1; DP[1] = 2;

    for(int i = 2; i < n; i++){
        DP[i] = (DP[i-2] + DP[i-1]) % 10007;
    }
    printf("%d", DP[n-1]);
}

 

📝 문제풀이 과정

---

2 x n 직사각형은 이전 직사각형에서 2 x 1 씩 늘어난다.

• 만약, 이전 DP[n-1]을 가져온다면 2 x 1을 하나 놓을 수 있고, DP[n-2]를 가져온다면 1 x 2를 두 개 놓는 방법이 있다.
• 따라서 DP[n]에서의 점화식 DP[n] = DP[n-2] + DP[n-1]이 된다.
• DP[n]에는 n-2, n-1이 필요하므로, DP[1] = 1, DP[2] = 1을 미리 선언해놓는다.

 

👏 결과

---