안녕하세요.
알고스팟의 문제는 아니지만 알고리즘 문제를 풀다가 아무리 생각해도 메모이제이션이 적용이 안되서 이렇게 질문합니다.
구종만 저자님께서 지으신 알고리즘 책을 보면서 공부하고 있는데요.
내용중에 '참조적투명한' 함수에서만 적용가능하다고 알고 있고 또 그것이 무엇인지 여러 문제를 풀면서 느꼈습니다. 하지만 아래 문제는 참조적 투명한것 같으면서도 아닌 것같기도 하고 아무리 메모이제이션을 적용하려 해도 시원하게 적용이 안되어 이렇게 질문드립니다.
일단 문제는 아래와 같습니다.

madam 을 스택에 넣어서 나온 결과중 adamm이라는 결과를 출력할 수 있는 경우의 수를 모두 출력하시오.

예)
---input----
madam

adamm

---output---
iiiioooioo
iiiiooooio
iioioioioo

iioioiooio

i는 스택에 push하라는 것이고 o는pop하라는 뜻입니다.
위처럼 madam에서 adamm이 될 수 있는 경우는 총 4가지 경우의 수가 존재하며 각 경우는 위와 같습니다.

전 이문제를 완전탐색에서 조금 변형하여 풀기는 했습니다만
몇가지 상황에서 완전탐색하는 것과 같은 시간 복잡도가 걸립니다.
변형한 것은 아래와 같습니다.

스택에서 pop을 했을때마다 답 문자열과 비교하여 다르면 리턴하는 식으로 변형했습니다.

하지만 아래와 같은 경우엔 완전탐색과 똑같이 동작합니다.

mmmma
mmmma
값이 같은 경우

mmmma
mmmam
같은 문자가 많은 경우

mmmma
mmmmd
처럼 끝에 있는 값이 다른 경우

제가 보기에는 이문제가 책의 예제 중 [삼각형 위의 최대 경로] 처럼 이전 상황을 전혀 신경쓰지 않고 앞으로의 결정만으로 답을 찾아낼 수 없을 것같아 보입니다.

아니면 아직 제가 찾지 못한 부분이 있는 것일까요??
문제에 대해서 어떤식으로 메모이제이션을 적용시키면 될지 조언을 해주시면 감사하겠습니다.