BOJ 1464 : 뒤집기 3

• 문제 링크 : boj.kr/1464
• 난이도 : G4
• 태그 : 그리디

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    string s;
    cin >> s;

    string ans = "";
    ans = ans + s[0];
    for(int i = 1; i < s.size(); i++) {
        if(ans[0] >= s[i]) {
            ans = s[i] + ans;
        }
        else {
            ans = ans + s[i];
        }
    }
    cout << ans;

    return 0;
}

---

풀이

처음부터 i만큼 뒤집을 수 있다는 것은 i번째 문자를 그 전까지의 문자열의 앞이나 뒤에 붙일 수 있다는 것을 의미한다.

i번째 문자를 앞에 붙여서 사전순으로 이득을 본다면 앞에, 아니라면 맨 뒤에 붙이면 된다.