← 返回题目列表

Codeforces · 954/A

A. 对角行走

中文机器翻译题面 查看原题

米哈伊尔在 2D 平面上行走。他可以向上或向右。您将获得米哈伊尔的一系列动作。他认为这个序列太长,他想让它尽可能短。

在给定的序列中,向上移动由字符 U 描述,向右移动由字符 R 描述。Mikhail 可以用对角线移动(描述为字符 D)替换任何一对连续移动 RU 或 UR。之后,他可以继续做一些其他的替换,直到没有一对连续的动作RU或UR剩下。

你的问题是打印替换后移动序列的最小可能长度。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 100) — 序列的长度。第二行包含由 n 个字符 U 和 R 组成的序列。

输出

在完成所有替换后打印移动序列的最小可能长度。

示例

输入 #1

5
RUURU

输出 #1

3

输入 #2

17
UUURRRRRUUURURUUU

输出 #2

13

注意

在第一个测试中,缩短的移动序列可能是 DUD(其长度为 3)。

在第二个测试中,缩短的移动序列可以是 UUDRRRDUDDUUU(其长度为 13)。