A+B 그리디 C++

[baekjoon 12904] A와 B (문자열, 그리디) (C++)

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 시작 단어에서 뒤에 A를 붙이거나, 단어를 뒤집어서 B를 붙이거나 해서 목표 단어까지 만들 수 있는지의 여부를 계산해내는 문제이다. 처음엔 아무 생각 없이 DFS로 매번 A를 붙이거나, B를 붙였더니 시간 초과가 났다. 그도 그럴 것이, 시작 단어가 1글자에서 시작하고 목표 단어가 1000 글자면 매 단계마다 2번 ^ 1000이다. 4글자 단어를 만드는데 2^..