[PS 백준 - 5.6] 11726번: 2*n 타일링

문제 정보

백준 11726번 - 바로가기

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

---

코멘트

• [Logic]
  이 문제도 1 또는 2로 분할하여 더하는 문제기 때문에 앞의 5.5번 01타일 문제와 로직이 완전히 동일하다. 따라서 5.5번에서 나머지만 10007로 변경하면 된다.

---

소스 코드

<바텀업 방식>

#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로 분할하는거랑 똑같은 문제 아닌가??
	arr[0] = 0;
	arr[1] = 1;
	arr[2] = 2;

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