백준 11726번, 2xn 타일링

백준 11726번 c++ 문제풀이

문제:

백준 11726

풀이:

1. 타일링의 규칙을 찾는다. dp[1] = 1
   dp[2] = 2
   dp[3] = 3
   dp[4] = 5
   dp[5] = 8
   위의 규칙을 따르면 점화식은 dp[n] = dp[n-1] + dp[n-2]
2. 주의할 점은 문제에서 10007로 나눈 값을 구하라고 되어있다. 마지막에만 나눠주면 될 것 같지만, 가장 dp[1000]은 long long 형으로도 감당하지 못할 큰 수이다.
   따라서 dp에 저장할 때 미리 나눠주는 절차를 밟아야 에러가 나지 않을 것이다.

코드:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long dp[1001];

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; 
    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];
    return 0;
} 

감사합니다.