Chopsticks(塗り箸) - joi2009-day4

出典: 第8回日本情報オリンピック 春季トレーニング合宿

時間制限: 1秒

メモリ制限: 64MB

漆塗りお箸協会(Japan Ohashi Institute) は, お箸の国際普及のためにデザインされたお箸を用意することになった. お箸のうち, 彩色される部分は一端から長さNmmにわたる部分で, 1mmごとに色が定まっており, 色が塗られない部分はない. また, お箸の彩色に使用する漆の色は52色である.

漆塗り職人のあなたは, 決められた色の通りに, お箸を塗る作業を依頼された. 漆塗りには手間がかかるため, なるべく少ない作業回数でお箸を完成させたい.

お箸を塗るための1 作業とは, 連続する区間を選び, その区間すべてを一色で塗ることである. この際, すでに色が塗られていた場所も必ず新しい色となる. お箸を完成させるために必要な作業回数の最小値を求めるプログラムを書け.

Input.

入力ファイルchopsticks.inの1行目には1つの整数N (1 ≤ N ≤ 300) が書かれている. これはお箸の彩色される部分の長さがNmmであることを表す.

2行目には, N文字からなる英字(A～Z, a～z) の列が与えられる. 文字列のi文字目が端から(i-1)mm からimmまでの色を表す.

Output.

出力は, 標準出力に行うこと. 作業回数の最小値を表す1つの整数を出力せよ.

採点基準

採点用データのうち, 配点の20% 分については, N ≤ 20 を満たし, 配点の40% 分については, N ≤ 120 を満たす.

例1

chopsticks.in	標準出力
6 JOIIOI	4

例2

chopsticks.in	標準出力
15 PlovdivBulgaria	12