경이로운 그리디 알고리즘4 -역으로 생각해서 경우의 수를 줄이는 테크닉-

1. 문제 12904번: A와 B (acmicpc.net) 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 2. 풀이 S에서 T를 만들려고만 한다면 이 문제가 상당히 어렵다 그냥 왠지 모르지만 어떤 문제든 역으로 시도해볼때 뭔가 보일수도 있다 조금 생각해보면 1) 문자열의 뒤에 A를 추가한다 2) 문자열을 뒤집고 뒤에 B를 추가한다 두 연산만으로 S에서 T가 만들어졌는데 문자열 T가 ABBA인 경우를 생각해보자. ABBA는 이전에 어떤 문자열이었을까? 오직 1가지인 ABB인..