[백준/C++] 1904번 : 01타일 (DP 연습)

01타일

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

예제 입력 1

4

예제 출력 1

5

---

해당 문제는 동적계획법(DP)를 활용하여 풀이하는 문제였다.

 

'00' 과 '1' 의 조합으로, N 자릿수만큼 만들 수 있는 가짓수를 전부 세는 문제였는데, 나는 처음에 단순무식하게 접근해서 직접 모든 경우의 수를 구했다.

❌ 직접 숫자를 구한 풀이

#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

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

	int N;
	cin >> N;
	
	vector<set<string>> dp(1000001);
	dp[1].insert("1");
	dp[2].insert("00");
	dp[2].insert("11");

	for(int i = 3; i <= N; i++)
	{
		for(auto iter = dp[i-1].begin(); iter != dp[i-1].end(); iter++)
		{
			dp[i].insert(*iter+"1");
			dp[i].insert("1"+*iter);
		}

		for (auto iter = dp[i - 2].begin(); iter != dp[i - 2].end(); iter++)
		{
			dp[i].insert(*iter + "00");
			dp[i].insert("00" + *iter);
		}
	}

	cout << dp[N].size();

	return 0;
}

 

dp[i] 배열은 i 자릿수에 들어가는 모든 문자열을 저장하도록 했고, STL set 자료구조를 사용하여 중복되는 문자열을 지울 수 있도록 구현하였다.

 

'00'은 2자릿 수이고, '1'은 1자릿 수이니까, 이전 자릿수의 결과에는 '1'을 앞뒤로 더하고, 2번째 이전 자릿수의 결과에는 '00'을 앞뒤로 구했다.

 

그러나 해당 방법은 시간도 시간이고, 메모리공간을 너무 많이 사용해야 해서 통과되지 못했다.

 

⭐ 규칙찾기

 

다른 풀이를 고민하면서 숫자들을 나열하고, 그 가짓수를 나열하는데 묘하게 어디선가 본 적 있는 수열같았다.

위에서 작성했던 코드가 메모리가 클 뿐 가짓수는 전부 정상으로 나왔기 때문에 6자릿수와 7자릿수의 결과도 확인할 수 있었다.

7자릿수까지 확인해보고 나서야, 결과의 가짓수가 '피보나치 수열'과 동일하다는걸 깨달았다.

 

⭕ 피보나치 수열을 이용한 풀이

#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

	int N;
	cin >> N;

	vector<int> dp(N + 1);
	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];

	return 0;
}

 

결과적으로 정답이 된 풀이는 피보나치 수열의 점화식을 사용하면 아~주 간단하게 풀리는 문제였다.

이때, N의 숫자 범위가 1,000,000까지 나올 수 있기에 문제에서 주어진 15746 숫자를 나눈 나머지 값으로 저장해주었다.

---

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

1904번: 01타일