moner_ari   9달 전

[문제]

Fernando는 얼마 전 시작한 개발 프로젝트를 끝마치기 위해 최근 워털루 대학교에 취직했다. 대학은 캠퍼스 바깥에 중요한 외부 방문객 및 협업자들을 위한 방갈로 거리를 건설하고 싶어한다.

현재 해당 거리는 일부 구간만 완성되었는데, 거리는 호숫가에서 시작해서 숲속의 어느 지점까지만 지어져 있다. Fernando가 해야할 일은 방갈로를 추가로 지어서 숲의 반대쪽 끝까지 거리를 연장하는 것이다. 현재 존재하는 모든 방갈로는 거리의 한쪽 면에만 있으며, 새롭게 지어질 방갈로 역시 같은 면에 지어져야 한다. 방갈로는 여러 종류가 있으며 다양한 색깔로 색칠되어 있다.

지금까지 지어진 거리의 전반적인 배치는 Fernando에게는 조금 혼란스러워 보인다. Fernando는 지금 생각하고 있는 디자인으로 방갈로를 지었을 때 거리가 더욱 어지러워 보일 것 같아서 걱정하고 있다. 어지러운 방갈로의 모습에 균형을 잡아주기 위해, Fernando는 새롭게 지을 방갈로의 색깔을 적절하게 선택해서 거리의 배치에 질서를 주고 싶어한다. 프로젝트가 완료되었을 때, 방갈로 색깔을 수열로 나타낸다면 해당 수열은 대칭을 이룰 것이다. 즉, 색깔을 순서대로 배치한 수열을 앞에서 관찰한 결과와 뒤에서 관찰한 결과가 서로 같아야 한다.

이때 앞서 언급한 조건을 충족하도록 방갈로를 짓고 적절하게 색을 칠했을 때, 새로 지어야 하는 방갈로의 최소 개수가 얼마나 되는지 Fernando는 궁굼해졌다. 그를 도와 새로 지어야 하는 방갈로의 최소 개수를 구하시오.

--------

[입력]

입력의 첫 줄에는 현재 거리에 지어진 방갈로의 개수를 의미하는 정수 N (1 ≤ N ≤ 4 · 105)이 주어진다. 다음 줄에는 거리의 시작점(호숫가)에서부터 현재 존재하는 방갈로의 색깔로 구성된 수열이 주어진다. 방갈로의 색깔로 구성된 수열은 N개의 알파벳 소문자(a~z)로만 구성되어 있으며, 각각의 문자는 방갈로의 색깔을 나타낸다.

--------

[출력]

Fernando가 제시한 조건을 충족하도록 방갈로의 색깔을 정할 때, 추가로 지어야 하는 방갈로의 최소 개수를 한 줄에 출력한다.

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