백준 16719 zoac

문제

https://www.acmicpc.net/problem/16719

설명

주어진 문자열에서 가장 작은거 출력하고 그다음 오른쪽으로 가다가 작은거 출력 오른쪽 다 했으면 왼쪽... , 사전순으로 출력하면되는 것이다.

주의

• 처음에 사전순인데 엥 왜 왼쪽에 붙는거지 싶었는데 기준은 원문자열이다 원래 문자열에서
  하나씩 떼면서 사전순으로 출력하는 것이다

• define MAX 999999999로 안하고 CPP안의 INFINITY를 사용했는데 틀렸고 define 값을 사용하니 맞았다 엥? INFINITY가 먼지 싶어서 cpp refer를 찾아보니
  Returns the special value "positive infinity", as represented by the floating-point type T.. 라고 나왔다 결론은 부동소수점에만 가능한 것이다.

• int는 무한대가 정의가 되어있지않고, 소수점은 정의가 되어있는데 그것은 infinity라고 한다.

소스

#include <bits/stdc++.h>

#define MAX 999999
using namespace std;

string str;
bool ch[101];

void dfs(int s, int e) {

    int minV = MAX, idx = -1;
    for (int i = s; i <= e; i++)
    {
        if (!ch[i] && minV > str[i]) {
            minV = str[i];
            idx = i;
        }
    }
    if (minV == MAX) return;  
    ch[idx] = 1;

    for (int i = 0; str[i]; i++) {
        //cout << "a";
        if (ch[i]) cout << str[i];
    }
    cout << endl;
    dfs(idx + 1, e);
    dfs(s, idx - 1);
}
int main() {

    cin >> str;

    dfs(0, str.size() - 1);

    return 0;
}