옻칠 젓가락 (Chopsticks)
면접 대비시간 제한1초메모리 제한1024 MB
길이 N인 목표 색 문자열이 주어질 때, 연속 구간을 한 가지 색으로 칠하는 연산만으로 그 문자열을 만드는 최소 연산 횟수를 구한다.
문제
옻칠 젓가락 협회(Japan Ohashi Institute)는 젓가락의 국제 보급을 위해 디자인된 젓가락을 준비하게 되었다. 젓가락에서 색이 칠해지는 부분은 한쪽 끝에서 길이 Nmm에 이르는 부분이며, 1mm마다 색이 정해져 있고 색이 칠해지지 않는 부분은 없다. 또한 젓가락을 칠하는 데 사용하는 옻의 색은 52색이다.
옻칠 장인인 당신은 정해진 색대로 젓가락을 칠하는 작업을 의뢰받았다. 옻칠에는 손이 많이 가므로, 가능한 한 적은 작업 횟수로 젓가락을 완성하고 싶다.
젓가락을 칠하는 1작업이란 연속한 구간을 골라 그 구간 전체를 한 가지 색으로 칠하는 것이다. 이때 이미 색이 칠해져 있던 곳도 반드시 새로운 색이 된다. 젓가락을 완성하기 위해 필요한 작업 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에는 정수 N (1 ≤ N ≤ 300)이 주어진다. 이는 젓가락에서 색이 칠해지는 부분의 길이가 Nmm임을 나타낸다.
둘째 줄에는 N글자로 이루어진 영문자 (A~Z, a~z) 열이 주어진다. 문자열의 i번째 글자는 끝에서 (i − 1)mm부터 imm까지의 색을 나타낸다.
출력
출력은 표준 출력으로 한다. 작업 횟수의 최솟값을 나타내는 정수 하나를 출력하시오.