[c++/백준] 1904번: 01타일

문제 링크

1904번: 01타일

풀이

전에 풀었던 타일링 문제랑 비슷한 dp 문제
1. n=0이면 아예 안 넣는 경우의 수 1, n=1이면 1 하나. 즉 dp[0]=1, dp[1]=1이다.
2. 이제 인덱스 2부터 구하는데, i-2번째에서 뒤에 00을 붙이는 경우의 수와, i-1번째에서 뒤에 1을 붙이는 경우의 수를 더해주면 i번째 값이 나온다.
즉, 점화식은 dp[n]=dp[n-2]+dp[n-1]이다.
3. 각각의 값을 갱신해주면서 15746 나머지 값을 넣어주고 dp[n]을 출력한다.

코드

#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
	int n;
	cin >> n;
	
	vector<int> dp(n+1);
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		dp[i] = (dp[i - 2] + dp[i - 1])%15746;
	}
	cout << dp[n];

	return 0;
}