접두사 뒤집기 3
시간 제한2초메모리 제한128 MB
문자열이 주어질 때 길이 1부터 N까지 순서대로 각 접두사를 뒤집을지 선택해서 얻을 수 있는 사전순으로 가장 작은 문자열을 구하는 문제입니다.
문제
길이가 N인 문자열 S가 주어진다. 정수 i를 1부터 N까지 차례대로 보며, 각 i마다 현재 문자열의 앞에서 정확히 i개의 문자를 뒤집을지 그대로 둘지 선택할 수 있다.
모든 선택을 마친 뒤 만들 수 있는 문자열 중 사전순으로 가장 앞서는 문자열을 출력하라.
입력
첫째 줄에 문자열 S가 주어진다.
S의 길이는 최대 50이고, 모든 문자는 알파벳 대문자이다.
출력
만들 수 있는 문자열 중 사전순으로 가장 앞서는 문자열을 출력한다.