자석
시간 제한1초메모리 제한128 MB
N개의 막대자석이 극에 따라 자동으로 붙는 상황에서 뒤집기를 최소로 사용해 길이가 정확히 L인 자석을 만드는 방법을 구합니다.
문제
동혁이는 길이가 1인 작은 막대 자석을 N개 가지고 있다. 각 자석은 왼쪽과 오른쪽 끝에 서로 다른 극(N극과 S극)이 있으며, 입력에는 왼쪽에서 오른쪽으로 본 극의 순서가 NS 또는 SN으로 주어진다.
서로 마주 보는 두 끝의 극이 다르면 두 자석은 붙고, 같으면 붙지 않는다. 이 자석들은 매우 강해서 한 번 붙으면 다시 떼어낼 수 없다. 실험을 시작하면 현재 서로 붙을 수 있는 이웃한 자석들이 모두 붙어 하나의 더 긴 자석이 된다. 붙어서 만들어진 자석도 하나의 자석으로 취급하며, 이 자석 전체를 뒤집을 수 있다. 자석을 뒤집으면 왼쪽과 오른쪽의 극이 서로 바뀐다. 뒤집은 뒤 이웃한 자석과 붙을 수 있으면 즉시 붙는다.
아래는 실험을 시작하기 전 자석 6개의 배치이다.
실험을 시작하면 네 번째와 다섯 번째 자석이 붙어 다음과 같이 된다.
초기 배치가 주어졌을 때, 길이가 정확히 L인 자석을 만들기 위해 필요한 뒤집기 횟수의 최솟값을 구하시오. 항상 길이가 정확히 L인 자석을 만들 수 있는 입력만 주어진다.
입력
첫째 줄에 자석의 수 N과 만들고 싶은 자석의 길이 L이 주어진다. (1 <= N <= 500000, 1 <= L <= N)
둘째 줄에는 초기 자석의 배치를 나타내는 문자열 NS 또는 SN이 N개 주어진다.
항상 답이 존재하는 경우만 주어진다.
출력
길이가 정확히 L인 자석을 만들기 위해 필요한 뒤집기 횟수의 최솟값을 출력한다.