[백준] 11726번 2 x n 타일링 C++

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

C++

#include<iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);

    // 2 x n 크기의 직사각형 1x2, 2x1로 채우는 방법의 수
    // 2xn 크기의 직사각형 채우는 방법의 수 10,007로 나눈 나머지

    int n; int arr[1001];
    arr[1] = 1; arr[2] = 2;
    cin >> n;


    for(int i = 3; i <= n; i++) {
        arr[i] = (arr[i-1] + arr[i-2]) % 10007;
    }
    cout << arr[n] << "\n";
}

문제풀이

• n = 1,2,3,4,5일 때의 방법을 모두 구해보면서 점화식을 찾았다. n = k일 때의 방법의 수는 k-1번째와 k-2번째의 방법의 수를 더하면 구해진다. 문제가 2xn 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 구하는 것이기 때문에 for문에서 바로 10,007의 나머지로 저장한다.

Comment

• DP 문제는 직접 쓰고 그려보면서 관계를 찾는 것이 중요하다