[BOJ] 백준 16719 ZOAC

문제링크 : https://www.acmicpc.net/problem/16719

 이 문제는 내 생각엔 DP 문제인듯 하다.
제일 작은 문자를 찾은 후, 그 오른쪽에서 제일 작은 문자를 찾는다.
이런식으로 가다가, 더이상 찾을만한 문자가 없을경우 왼쪽에서 찾는다.

즉 작은 단위로 쪼개서 그 단위를 가지고 큰 문제를 만든다는점에서,
그리고 전부 넣어보는게 아닌 제일 작은 문자 만을 찾고 그곳을 기준으로 한다는 점이
브루트포스와는 차별화 된 것 같다.


소스코드 :

#include 
#include 
using namespace std;

char * ch;

void Func(string & str, int s, int e) {
 if (s == e) return;
 if (s < 0) return;
 if (e > str.length()) return;
 int small = 987654321;
 int index = -1;
 for (int i = s; i < e; i++) {
  if (str[i] < small) {
   small = str[i];
   index = i;
  }
 }
 ch[index] = str[index];

 for (int i = 0; i < str.length(); i++) {
  if (isalpha(ch[i])) cout << ch[i];
 }
 cout << endl;
 Func(str, index + 1, e);
 Func(str, s, index);

}

int main() {

 string str;
 getline(cin, str);
 ch = new char[str.length()];
 for (int i = 0; i < str.length(); i++) {
  ch[i] = '*';
 }
 Func(str, 0, str.length());


 return 0;
}