[백준 11726] 2×n 타일링

0. 제목

• 백준 11726 2xn 타일링
• BOJ 11726 2xn 타일링
• C++ 2xn 타일링

---

1. 문제

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

---

2. 풀이

• DP 방식을 이용하였다.
• 초기값 2개(dp[1], dp[2])를 먼저 설정하고 가로의 길이가 1씩 증가할 때 어떻게 변할지 생각해보았다.
• 가로의 길이가 1 증가했을 때의 답은 마지막에 세로로 타일 한개를 놓는 방법(dp[i-1])과 마지막전까지 해서 가로로 타일 두개를 놓는 방법(dp[i-2])를 합한 값이 방법의 수가 된다.
• 반복문을 다 돌고 10007로 나누려면 수가 너무 커지기 때문에 dp[i]를 구할때 마다 10007로 나눈 나머지를 구해준다.

---

3. 코드

#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int n;
    int dp[1001]={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; //dp[3]=dp[2]+dp[1], dp[4]=dp[3]+dp[2]
    }
   cout << dp[n] << '\n';
    return 0;
}