티스토리 뷰

알고리즘 관련/BOJ

BOJ)1251 단어 나누기

JASON 자손9319 2017. 4. 20. 16:44

문제: icpc.me/1251


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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(000);
    sort(vt.begin(), vt.end());
    cout << vt[0<< "\n";
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)5913 준규와 사과  (0) 2017.04.21
BOJ)3109 빵집  (0) 2017.04.21
BOJ)1251 단어 나누기  (0) 2017.04.20
BOJ)14503 로봇 청소기  (0) 2017.04.17
BOJ)14500 테트로미노  (4) 2017.04.17
BOJ)14501 퇴사  (0) 2017.04.17
댓글
댓글쓰기 폼