[PS 백준 - 5.7] 11727번: 2*n 타일링 2

문제 정보

백준 11727번 - 바로가기

• 난이도: 실버 3
• 알고리즘: 다이나믹 프로그래밍

---

코멘트

• [Logic]
  이 문제도 1 또는 2로 분할하여 더하는 문제지만, 2로 분할할때 가로 세로 두 방향이 존재한다. 따라서 앞의 5.6번 2*n 타일링 문제에서 2로 분할하는 경우에 곱하기 2만 해주면 된다.

---

소스 코드

<바텀업 방식>

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

long long int arr[1000001];

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

	// 1, 2로 분할하는거랑 똑같은데 2가 되는 가짓수가 2개씩 존재
	arr[0] = 0;
	arr[1] = 1;
	arr[2] = 3;

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