[C++] 백준 1904 01타일

#include <iostream>

using namespace std;

int n;
int dp[1000001];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	dp[1] = 1;
	dp[2] = 2;

	for (int i = 3; i <= n; i++)
	{
		dp[i] = (dp[i - 2] + dp[i - 1]) % 15746;
	}

	cout << dp[n];
}

 

풀이

1. 점화식을 잘 짜야한다.

2. 1개일때 1, 2개일때 00 11, 3개일때 111 001 100, 4개일때 1111 1100 0011 1001 0000이므로

1 = 1, 2 = 2, 3 = 3, 4 = 5

3개일때부터 전의 두개의 합과 같으므로

dp[i] = (dp[i - 2] + dp[i - 1]) % 15746;

의 식이 된다.

 

4. O(n)보다 빠르게 풀어야한다. 값이 커져서 문제에서 15746으로 나눈 나머지를 출력한다.

n이 1000000이므로 O(n²)이면 경우의 수가 너무 많아진다.

 

느낀점

- 뭔가를 나눈 값을 출력하게된다면 동적계획법인듯하다.