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

📝 문제풀이 과정

---

2 x n은, n-1번째에서 2 x 1이 추가된 경우, n-2번째에서 1 x 2 2개가 추가되거나 2 x 2 1개가 추가된 경우로 생각해볼 수 있다.

n-2에서의 두 가지 경우를 어떻게 점화식으로 표현할까 생각했는데, 그냥 DP[n-2]를 2개 써보자 라고 생각했다.

따라서, 점화식은

DP[n] = DP[n-1] + DP[n-2] + DP[n-2]

이렇게 된다.

여기서 초기값으로 DP[0]과 DP[1], 즉 n = 1인 경우와, n = 2인 경우의 값이 필요하다.

DP[0] = 1, DP[1] = 2이다.

 

💻 C++ 제출코드

---

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);

    vector<int> DP(n);

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

}

 

👏 결과

---