우표 검사 구간

문제

한 우체국은 긴 받침대에 편지를 왼쪽부터 한 줄로 올려놓고 우표 부착 상태를 검사한다. 받침대에는 번호가 작은 자리부터 큰 자리까지 빈자리 없이 편지가 한 통씩 놓여 있다. 검사 담당자는 각 편지의 상태를 확인한 뒤, 우표가 제대로 붙어 있으면 문자 P를 쓰고 우표를 다시 붙여야 하면 문자 X를 쓴다. 이렇게 만든 문자열의 왼쪽 문자는 받침대의 왼쪽 편지에 대응한다. 우표를 다시 붙이는 직원은 작업을 시작할 때마다 받침대의 한 구간을 선택한다. 한 구간은 서로 이웃한 편지들로 이루어져야 하며, 그 안의 모든 편지 상태가 X여야 한다. 상태가 P인 편지를 구간 안에 포함할 수는 없다. 선택한 구간의 편지에는 한 번의 작업으로 모두 새 우표를 붙일 수 있다. 구간의 길이에 따른 추가 제한은 없다. 직원은 상태가 X인 모든 편지를 처리하려고 한다. 작업 전에 편지를 옮기거나 순서를 바꿀 수 없고, 서로 떨어진 두 구간을 한 번의 작업으로 처리할 수도 없다. 다만 X가 연속해서 놓여 있다면 그 편지들은 길이에 관계없이 하나의 구간으로 묶을 수 있다. 처리한 편지는 다시 처리할 필요가 없으며, 작업 결과가 다른 편지의 상태를 바꾸지는 않는다. 예를 들어 두 편지 사이에 P가 하나라도 있다면, 두 편지의 상태가 모두 X이더라도 같은 작업 구간에 포함할 수 없다. 반대로 받침대의 맨 왼쪽이나 맨 오른쪽에 X가 놓여 있어도 별도의 예외 규칙은 없다. 그 자리에서 시작하거나 끝나는 구간을 선택하면 된다. 받침대의 양 끝은 서로 이웃한 것으로 보지 않는다. 편지 수 N과 검사 결과 문자열 S가 주어진다. 상태가 X인 모든 편지에 새 우표를 붙이는 데 필요한 작업 횟수의 최솟값을 구한다. 모든 편지의 상태가 P라면 작업할 편지가 없으므로 답은 0이다. 출력에는 최소 작업 횟수만 적으며, 실제로 선택한 구간의 위치는 적지 않는다.

입력

첫째 줄에 편지 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 1,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S의 각 문자는 P 또는 X이다.

출력

필요한 작업 횟수의 최솟값을 정수 하나로 출력한다.

10
XXPXXXPPXP

3

5
PPPPP

0

1
X

1

출처: Devin.KR 자체 제작