백준 2963 무한 이진 트리 탐색
틀린 풀이
- 최악의 경우 BFS의 시간 복잡도 3^10000
-> 시간 초과 & 메모리 초과
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
ull sum = 0;
string input;
void bfs() {
queue<pair<ull, int>> q;
q.push(make_pair(1, 0));
while (!q.empty()) {
pair<ull, int> cur = q.front();
ull curnode = cur.first;
int curindex = cur.second;
q.pop();
while (curindex < input.size()) {
if (input[curindex] == 'L')
curnode = curnode << 1;
if (input[curindex] == 'P')
curnode = curnode;
if (input[curindex] == 'R')
curnode = (curnode << 1) + 1;
if (input[curindex] == '*')
break;
++curindex;
}
if (curindex == input.size()) {
sum += curnode;
continue;
}
q.push(make_pair(curnode << 1, curindex + 1));
q.push(make_pair(curnode, curindex + 1));
q.push(make_pair((curnode << 1) + 1, curindex + 1));
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> input;
bfs();
cout << sum;
return 0;
}