[알고리즘] C++ 백준 1904 01타일

백준 1904

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

1904번: 01타일

풀이 전 나의 생각

타일을 이용하여 2진 수열을 만드려고 한다. 하지만 0의 쓰여진 모든 타일들은 한 쌍으로 이루어진 00타일이 됐다.

이 조건을 만족하면서 자연수 N에 대해 최대로 만들 수 있는 2진 수열을 구해내야 한다.

 

우선 N이 1 부터 4까지 있다고 가정할 때 경우의 수를 구해보면

N = 1 -> 1

N = 2 -> 00, 11

N = 3 -> 000, 111, 100

N = 4 -> 0001, 1111, 1001, 0000, 1100

이렇게 나오게 된다.

 

여기서 N = 3인 경우를 살펴보면 000, 111인 부분이 N = 2일 때 00, 11값 뒤에 0과 1을 붙여주면 같은 값이 나오게된다.

나머지 100은 N = 1일 때 1에 00을 붙여주면 값이 같아진다.

 

다음으로 N = 4인 경우를 살펴보면 0001, 1111, 1001은 N = 3일 때 000, 111, 100 뒤에 0과 1을 붙여주면 값이 값이 나오게된다. 나머지 0000, 1100은 N = 2일 때 00, 11 에 00을 붙여주면 값이 같아진다.

 

N이 3과 4인 경우를 봤을 때 어떤 자연수 N에 대한 2진 수열은 이전 2진 수열 값에 어떠한 값을 더해주면 구해줄 수 있다는

결론이 나오게된다.

 

이를 점화식으로 표현하면 DP[N] = DP[N - 1] + DP[N - 2]가 나오게 된다.

(DP[4] = DP[3] + DP[2] -> N이 4일 때 3과 2의 2진 수열값을 더하면 4의 2진 수열값이 나온다.)

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>

int dp[1000001];

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n = 0;
	cin >> n;
	
	dp[1] = 1;
	dp[2] = 2;

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

	cout << dp[n];
}