#2052. HOUSE

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Nguồn: Free Contest 7

Trên một con đường có n tòa nhà. Mỗi tòa nhà được sơn bằng một màu Đỏ, Vàng, Xanh, hoặc Tím. Người ta muốn sơn lại một số tòa nhà (bằng một trong các màu Đỏ, Vàng, Xanh, Tím) sao cho không có hai tòa nhà liên tiếp có cùng màu sơn. Tìm số nhà cần sơn lại ít nhất.

Dữ liệu vào:

  • Dòng đầu tiên chứa số nguyên dương n\ (1 ≤ n ≤ 2500) ;
  • Dòng tiếp theo chứa một xâu kí tự có độ dài n , mỗi kí tự đại diện cho một tòa nhà. Mỗi kí tự có thể là D, V, X , hoặc T , lần lượt đại diện cho một ngôi nhà được sơn màu Đỏ, Vàng, Xanh, hoặc Tím.

Dữ liệu ra:

  • In ra số lượng nhà cần sơn lại ít nhất.

Ví dụ:

Dữ liệu vào:
2
TX
Dữ liệu ra:
0
Dữ liệu vào:
3
TXV
Dữ liệu ra:
0
Dữ liệu vào:
14
VVXDDTXVTXDVXV
Dữ liệu ra:
2
Dữ liệu vào:
17
DDTVVTDVVVTVVTDVV
Dữ liệu ra:
5