[PS 백준 - 5.5] 1904번: 01타일

문제 정보

백준 1904번 - 바로가기

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

---

코멘트

이제부터 나오는 문제들은 대부분 앞의 $4$문제 ($5.1 \sim 5.4$) 와 코드가 거의 비슷하다. DP 1 문제들은 거의 동일한 유형이라 보면 된다.

• [Logic]
  n=$1$부터 $5$까지만 나열해봐도 나 피보나치 문제에요~ 하는 것을 쉽게 알 수 있다. 피보나치 수열이기 때문에 단순히 바텀업으로만 구현했다.

---

소스 코드

<바텀업 방식>

#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] % 15746) + (arr[i - 2] % 15746)) % 15746;
	}
	cout << arr[n];
}