[Programmers] 2 x n 타일링 - travelbeeee

---

[ 알고리즘풀이 ]

 DP 문제로 DP[N] : 2 x N 타일링하는 경우의 수라고 한다면, 2 x N 타일링은 2 x (N - 1) 타일링 방법에 세로 한 줄을 추가하는 경우의 수와 2 X (N - 2) 타일링 방법에 가로 두 줄을 추가하는 경우의 수의 합으로 다음과 같은 점화식이 성립합니다.

■ DP[N] = DP[N - 1] + DP[N - 2]

 이때, 여러개의 테스트 케이스에 대해서 2 x N 타일링하는 경우의 수를 출력하는 게 아니라 단 한 번만 출력하면 되므로 굳이 배열을 선언해 메모리를 낭비하지 않고 2 x N 타일링하는 경우의 수를 앞에서부터 차곡차곡 쌓아가면 됩니다.

#include <string>
#include <vector>
#define M 1000000007
using namespace std;

int solution(int n) {
    int answer = 0, left = 0, right =1, temp;
    for(int i = 2; i <= n; i++){
        temp = (left + right) % M;
        left = right;
        right = temp;
    }
    answer = (left + right) % M;
    return answer;
}

---