문제.

문제 풀이 전략

1. 완탐인가?

• 문제를 읽어보면, 매순간 2개의 경우를 선택할 수 있기 때문에
  완탐으로 진행하면
  s : 1 자리, t가 1000 자리 라고 한다면
  시간 복잡도는 2의 (1000-1) 승이기 때문에
  -> 완탐으로는 풀 수 없다.

2. dp 인가??

• 그렇다고 규칙성도 없기 때문에 dp도 아니다... '

3. 그럼 뭘까???

• 특정 타겟값을 잡아서 처리하는 것이 아니므로 최적화 결정도 아니다.

• 그럼 아이디어 명제를 이용한 그리디이다...

4. 그리디

• 문제를 보면, 구해야 하는 값은 t값이다.

• 문제에 있는 그대로 진행한다면 수정해야 하는 값은 s인데..
  -> 문제를 믿지 말고, 생각해보면다면 고정되어 있는값은 t이다.

• t를 이용해서 s를 구할 수 있을까?? 라는 생각을 해야 한다.
  어떻게 이런 생각을 할 수 있을까?
  1) 어쨋든 s를 이용해 완탐으로는 못한다.
  2) 문제의 연산 2개를 읽어보면
  - 가) 문자열의 뒤에 a를 추가
  - 나) 문자열 뒤집고 b를 추가한다.
  -> 공통점으로는 문자열의 뒤에다가 뭔가를 추가한다는 것이다.
  

• 결론 :완성된 친구 입장에서 보면 마지막 abba가 완성될때는

명제를 통해서 구현

• 가) 연산을 통해서 만들어졌구나??? 를 생각할 수 있고,
  -> a를 제거 하면 abb가 남고,
  -> b를 제거 한 후 뒤집으면 ba가 되고
  -> a를 제거하면 b가 된다.
  -> 그럼 t에서 s를 구할 수 있네??

• 이제는 t를 이용해서 s를 구해보자.
  그런데 연산 2개는 다르게 접근해야 한다.