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

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

풀이

문제의 직사각형을 채우는 방법은 2*1 조각 1개 또는 1*2 조각 2개 (결국 2*2 모양)를 배치하는 것이다. 즉, 가로 길이가 1 채워지거나, 2 채워진다.

dp(i)를 가로 길이가 i인 직사각형을 채우는 경우의 수라고 정의하자.
가로 길이가 1 채워지는 경우 = dp(i-1)
가로 길이가 1 채워지는 경우 = dp(i-2)

따라서 dp(i) = dp(i-1) + dp(i-2)이다.

이는 피보나치 수열과 동일하고, 코드를 작성할 때 배열이나 벡터를 선언하는 대신 변수 2개에 dp(i-1), dp(i-2)를 저장하면 메모리 차지를 줄일 수 있다.

코드

#include <iostream>
using namespace std;

int main()
{
    int n;
    int a = 1, b = 2, c;
    
    cin >> n;
    
    if(n == 1) cout << a;
    else if(n == 2) cout << b;
    else {
        for(int i=3; i<=n; i++){
            c = (a + b) % 10007;
            a = b;
            b = c;
        }
        cout << c;
    }
    
    return 0;
}