b2r   7달 전

이 문제에서 정의한 '문자열 회전'은 구간 $[l, r]$의 순서를 뒤집는 Reverse 연산이다. 문제에서 주어진 시행 횟수 최대 $N$번은 문자열의 모든 문자를 우리가 원하는 위치로 재배치하기에 충분한 횟수이다.

문자열 $S$의 $i$번째 문자를 $a_i$라고 하자. 우리가 만들고 싶은 목표 문자열을 앞에서부터 채워나가는 전략을 사용한다.

$i$번째 자리에 놓아야 할 문자가 현재 $k$번째 위치($k \ge i$)에 있다면, 구간 $[i, k]$를 뒤집어 해당 문자를 $i$번째로 보낼 수 있다.

이 과정에서 이미 맞추어 놓은 $1$ ~ $i-1$번째 문자들은 뒤집기 범위 밖에 있으므로 위치가 변하지 않는다.

이 방법을 반복하면 문자열 전체를 원하는 대로 재배치하는 데 최대 $N$번의 연산이 필요하며, 이는 문제의 제한 조건 내에서 항상 가능하다.

결국 이 문제는 처음 위치와 상관없이, 현재 보유한 알파벳 재료(G, S, H)를 조합하여 GSHS라는 세트를 최대 몇 개 만들 수 있는지를 묻는 문제로 귀결된다.

GSHS 한 세트를 만들기 위해 필요한 각 문자의 개수는 다음과 같다.

G: 1개

S: 2개

H: 1개

문자열 $S$에 포함된 각 문자의 전체 개수를 $g, s, h$라고 할 때, 정답은 다음과 같다.

$$\text{정답} = \min(g, s/2, h)$$

댓글을 작성하려면 로그인해야 합니다.