[알고리즘] 01타일 (bk_2748)
문제
지원이에게 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인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.
생각한 알고리즘
# 1
1
# 2
00 , 11
# 3
001, 100 , 111
# 4
0000, 0011, 1100, 1111, 1001
# 5
00001, 00100, 10000, 11100, 11001, 10011, 00111, 11111
- 첫번째 알고리즘
- n-1번째 01타일에 타일 1을 추가했을 때의 경우의 수 + n-2번째 01타일에 타일 00을 추가했을 때의 경우의 수
- 2진수를 다뤄서 하고 있지만, 본 알고리즘은 10진수를 다룰 생각이다.
- 2진수 상에서 1을 추가 할때
- 앞, 뒤에 1 추가 가능하다.
- 앞에 1 추가 하는것은 기존 2진수의 10 진수에서 2^n을 더하는 값과 같다.
- 뒤에 1을 추가 하는 것은 기존 2진수의 10 진수에서 2를 곱하고 1을 더하는 값과 같다.
- 2진수 상에서 00을 추가 할 때
- 앞, 뒤에 00을 추가 가능하다.
- 앞에 00을 추가하는 것은 기존 수와 같다.
- 앞에 00을 추가하는 것은 4(2^2)를 곱하는 값과 같다.
- 2진수 상에서 1을 추가 할때
- 중복되는 수를 제외하고 개수를 더한다.
- 다음 알고리즘은 시간초과 이다.
- 해당 코드를 돌려보면 규칙을 찾아낼 수 있다.
#include <iostream>
#include <vector>
#include <utility> // pair
#include <bitset>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> v_n2; // n-2 번째의 이진 타일들을 담고 있는 배열
vector<int> v_n1; // n-1 번째의 이진 타일들을 담고 있는 배열
void fill_tile(int n)
{
vector<int> v_n;
if(n == 1)
{
v_n1.push_back(1);
}
else if(n == 2)
{
v_n2.push_back(1);
v_n1.push_back(3);
v_n1.push_back(0);
}
else{
fill_tile(n-1);
for (vector<int>::size_type i = 0; i < v_n2.size(); i++)
{
/* v_n does not contains item*/
if( v_n.empty() || find( v_n.begin(), v_n.end(), v_n2[i]) == v_n.end())
{
v_n.push_back(v_n2[i]);
}
/* v_n does not contains item*(2^2) */
if( v_n.empty() || find( v_n.begin(), v_n.end(), v_n2[i]*4 ) == v_n.end())
{
v_n.push_back(v_n2[i]*4);
}
}
for (vector<int>::size_type i = 0; i < v_n1.size(); i++)
{
/* v_n does not contains item */
if( v_n.empty() || find( v_n.begin(), v_n.end(), v_n1[i] + pow(2,n-1)) == v_n.end())
{
v_n.push_back(v_n1[i] + pow(2,n-1));
}
/* v_n does not contains item*(2^2) */
if( v_n.empty() || find( v_n.begin(), v_n.end(), v_n1[i]*2 + 1 ) == v_n.end())
{
v_n.push_back(v_n1[i]*2 + 1);
}
}
v_n2.resize((int)(v_n1.size()));
copy(v_n1.begin(), v_n1.end(), v_n2.begin() );
v_n1.resize((int)(v_n.size()));
copy(v_n.begin(), v_n.end(), v_n1.begin() );
}
}
int main()
{
int n;
cin>>n;
fill_tile(n);
cout<<v_n1.size();
}
$ g++ bk_1904.cpp
$ ./a.out
1
1
$ ./a.out
2
2
$ ./a.out
3
3
$ ./a.out
4
5
$ ./a.out
5
8
$ ./a.out
6
13
$ ./a.out
7
21
$ ./a.out
8
34
...
$ ./a.out
13
377
$ ./a.out
14
610
$ ./a.out
15
987
$
arr[n] = arr[n-1] + arr[n-2]
- 두번째 알고리즘
- 다음 점화식을 재귀를 이용하여 작성한다.
- n 이 260000을 넘어서면
Segmentation fault가 뜬다.
#include <iostream>
using namespace std;
int arr[11000000]= {0,};
int fill_tile(int n)
{
if(n<= 2)
{
arr[n] = n;
return n;
}
else
{
if(arr[n] > 0)
{
return arr[n];
}
else
{
arr[n] = (fill_tile(n-1) + fill_tile(n-2)) % 15746;
return arr[n];
}
}
}
int main(void)
{
int n;
cin>>n;
fill_tile(n);
cout<<arr[n];
return 0;
}
- 세번째 알고리즘
- 다음 점화식을 for문을 이용하여 작성한다.
#include <iostream>
using namespace std;
int main(void)
{
int n;
cin>>n;
int arr[1100000]= {0,};
for(int i = 1; i<= n; i++)
{
if(i<= 2)
{
arr[i] = i;
}
else
{
arr[i] = (arr[i-1] + arr[i-2]) % 15746;
}
}
cout<< arr[n];
return 0;
}