https://www.acmicpc.net/problem/12919
1. 거꾸로탐색
/*
* 이진탐색 -> 2^50 -> 시간초과
* 역발상 : target에서 start로 수렴하도록 변경!
*/
2. 전체코드
#include <bits/stdc++.h>
using namespace std;
string s, t,temp;
int ret;
//현재k문자열이 만들어짐
void dfs(string k) {
//cout << k << "\n";
//if (k.size()>t.size()) return;
if (s == k) {
ret = 1;
return;
}
//k를 삭제하다가 빈문자열이 되는경우 -> 가망없음
if (s.size() >= k.size()) return;
if (k.back() == 'A') {
temp = k;
temp.pop_back();
dfs(temp);
}
if (k[0] == 'B') {
temp = k;
temp.erase(temp.begin());
reverse(temp.begin(), temp.end());
dfs(temp);
}
return;
}
int main() {
/*
* 이진탐색 -> 2^50 -> 시간초과
* 역발상 : target에서 start로 수렴하도록 변경!
*/
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> s >> t;
dfs(t);
cout << ret;
return 0;
}
'Algorithm > 완전탐색' 카테고리의 다른 글
백준 1107 리모컨 c++ // 완탐, 초기값 잘 설정하는법 (0) | 2023.11.28 |
---|---|
프로그래머스 모의고사 c++ // 완전탐색 (0) | 2023.10.12 |