[백준][C++]1904번. 01타일

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

 

 

시간제한이 0.75초 라서 점화식을 찾고 이를 동적 계획법으로 풀어서 시간 복잡도를 줄여야한다. 

일단 쓸 수 있는 타일은 00 또는 1 이다.

1번째일때, 1개

2번째일때, 2개이다. 

이후를 생각해보자면 

1을 붙이는 경우는  n-1길이의 숫자 뒤에 붙이면 된다.

00을 붙이는 경우는 n-2길이의 숫자 뒤에 붙이면 된다. 

이를 통해 점화식 dp[n] = dp[n-1] + dp[n-2] 

즉 n-1에 1을 붙이는 경우와 n-2에 00을 붙이는 경우를 더 해주면 되는 것이다.

 

정답코드

#include <iostream>

using namespace std;

//dp활용 : 점화식을 구해야한다.
int main()
{
	int n;

	cin >> n;

	if (n == 1)
	{
		cout << 1 << endl;
		return 0;
	}

	int p1 = 1;			//p[n-2]
	int p2 = 2;			//p[n-1]
	int p_n = 0;

	//dp계산
	for (int i = 3; i <= n; i++)
	{
		p_n = (p1 + p2) % 15746;
		p1 = p2;
		p2 = p_n;
	}

	cout << p2 << endl;

	return 0;
}