BOJ)1251 단어 나누기

문제: icpc.me/1251

단어를 세 단어로 나눈 뒤 나눈단어를 전부 뒤집어 다시 붙인 단어들 중 사전순으로 가장 앞서는 단어를 출력하는 문제이다.

N이 50까지 밖에 안들어오기 때문에 가능한 경우를 전부 뽑아내도 50C3  밖에 안되므로 모든 경우를 탐색하여 결과를 확인해주면 된다.

#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<string> vt;
string a;
void rev(string &x, int lo, int hi) {
    string z = x;
    for (int i = lo; i <= hi; i++)
        x[i] = z[lo + hi - i];
}
void func(int pos, int cnt, int mid) {
    if (!cnt) {
        if (pos >= a.length() - 2)
            return;
        func(pos + 1, cnt + 1, pos);
        func(pos + 1, cnt, mid);
    }
    else if (cnt == 1) {
        if (pos >= a.length() - 1)
            return;
        func(pos + 1, cnt, mid);
        string b = a;
        rev(b, 0, mid);
        rev(b, mid + 1, pos);
        rev(b, pos + 1, b.length() - 1);
        vt.push_back(b);
        return;
    }
}
int main() {
    cin >> a;
    func(0, 0, 0);
    sort(vt.begin(), vt.end());
    cout << vt[0] << "\n";
    return 0;
}