시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB115166146535553.518%

문제

십년이면 강산이 변한다.

강산이네 동네에 드디어 극장이 생겼고, 강산이는 극장에 놀러갔다. 매점에서 콜라를 산 뒤, 자리에 앉은 강산이는 큰 혼란에 빠졌다. 양쪽 컵홀더를 이미 옆 사람들이 차지했기 때문에 콜라를 꽂을 컵 홀더가 없었기 때문이다. 영화를 보는 내내 콜라를 손에 들고 있던 강산이는 극장에 다시 왔을 때는 꼭 콜라를 컵 홀더에 놓겠다는 다짐을 한 후 집에 돌아갔다.

극장의 한 줄에는 자리가 N개가 있다. 서로 인접한 좌석 사이에는 컵홀더가 하나씩 있고, 양 끝 좌석에는 컵홀더가 하나씩 더 있다. 또, 이 극장에는 커플석이 있다. 커플석 사이에는 컵홀더가 없다.

극장의 한 줄의 정보가 주어진다. 이때, 이 줄에 사람들이 모두 앉았을 때, 컵홀더에 컵을 꽂을 수 있는 최대 사람의 수를 구하는 프로그램을 작성하시오. 모든 사람은 컵을 한 개만 들고 있고, 자신의 좌석의 양 옆에 있는 컵홀더에만 컵을 꽂을 수 있다.

S는 일반 좌석, L은 커플석을 의미하며, L은 항상 두개씩 쌍으로 주어진다.

어떤 좌석의 배치가 SLLLLSSLL일때, 컵홀더를 *로 표시하면 아래와 같다.

*S*LL*LL*S*S*LL*

위의 예에서 적어도 두 명은 컵홀더를 사용할 수 없다.

입력

첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다.

출력

컵을 컵홀더에 놓을 수 있는 최대 사람의 수를 출력한다.

예제 입력 1

3
SSS

예제 출력 1

3

예제 입력 2

4
SLLS

예제 출력 2

4

예제 입력 3

9
SLLLLSSLL

예제 출력 3

7
W3sicHJvYmxlbV9pZCI6IjI4MTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlZjVcdWQ2NDBcdWIzNTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzJlZFx1YjE0NFx1Yzc3NFx1YmE3NCBcdWFjMTVcdWMwYjBcdWM3NzQgXHViY2MwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMTVcdWMwYjBcdWM3NzRcdWIxMjQgXHViM2Q5XHViMTI0XHVjNWQwIFx1YjRkY1x1YjUxNFx1YzViNCBcdWFkZjlcdWM3YTVcdWM3NzQgXHVjMGRkXHVhY2JjXHVhY2UwLCBcdWFjMTVcdWMwYjBcdWM3NzRcdWIyOTQgXHVhZGY5XHVjN2E1XHVjNWQwIFx1YjE4MFx1YjdlY1x1YWMxNFx1YjJlNC4gXHViOWU0XHVjODEwXHVjNWQwXHVjMTFjIFx1Y2Y1Y1x1Yjc3Y1x1Yjk3YyBcdWMwYjAgXHViNGE0LCBcdWM3OTBcdWI5YWNcdWM1ZDAgXHVjNTQ5XHVjNzQwIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YjI5NCBcdWQwNzAgXHVkNjNjXHViNzgwXHVjNWQwIFx1YmU2MFx1Yzg0Y1x1YjJlNC4gXHVjNTkxXHVjYWJkIFx1Y2VmNVx1ZDY0MFx1YjM1NFx1Yjk3YyBcdWM3NzRcdWJiZjggXHVjNjA2IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWNjMjhcdWM5YzBcdWQ1ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Y2Y1Y1x1Yjc3Y1x1Yjk3YyBcdWFmNDJcdWM3NDQgXHVjZWY1IFx1ZDY0MFx1YjM1NFx1YWMwMCBcdWM1YzZcdWM1YzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWM2MDFcdWQ2NTRcdWI5N2MgXHViY2Y0XHViMjk0IFx1YjBiNFx1YjBiNCBcdWNmNWNcdWI3N2NcdWI5N2MgXHVjMTkwXHVjNWQwIFx1YjRlNFx1YWNlMCBcdWM3ODhcdWIzNTggXHVhYzE1XHVjMGIwXHVjNzc0XHViMjk0IFx1YWRmOVx1YzdhNVx1YzVkMCBcdWIyZTRcdWMyZGMgXHVjNjU0XHVjNzQ0IFx1YjU0Y1x1YjI5NCBcdWFmMmQgXHVjZjVjXHViNzdjXHViOTdjIFx1Y2VmNSBcdWQ2NDBcdWIzNTRcdWM1ZDAgXHViMTkzXHVhY2EwXHViMmU0XHViMjk0IFx1YjJlNFx1YzlkMFx1Yzc0NCBcdWQ1NWMgXHVkNmM0IFx1YzlkMVx1YzVkMCBcdWIzY2NcdWM1NDRcdWFjMTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOVx1YzdhNVx1Yzc1OCBcdWQ1NWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YjlhY1x1YWMwMCBOXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjMTFjXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWM4OGNcdWMxMWQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1Y2VmNVx1ZDY0MFx1YjM1NFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNzg4XHVhY2UwLCBcdWM1OTEgXHViMDVkIFx1Yzg4Y1x1YzExZFx1YzVkMFx1YjI5NCBcdWNlZjVcdWQ2NDBcdWIzNTRcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YjM1NCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHVjNzc0IFx1YWRmOVx1YzdhNVx1YzVkMFx1YjI5NCBcdWNlZTRcdWQ1MGNcdWMxMWRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWNlZTRcdWQ1MGNcdWMxMWQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1Y2VmNVx1ZDY0MFx1YjM1NFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOVx1YzdhNVx1Yzc1OCBcdWQ1NWMgXHVjOTA0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjNzc0IFx1YzkwNFx1YzVkMCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHViYWE4XHViNDUwIFx1YzU0OVx1YzU1OFx1Yzc0NCBcdWI1NGMsIFx1Y2VmNVx1ZDY0MFx1YjM1NFx1YzVkMCBcdWNlZjVcdWM3NDQgXHVhZjQyXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjZWY1XHVjNzQ0IFx1ZDU1YyBcdWFjMWNcdWI5Y2MgXHViNGU0XHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Yzg4Y1x1YzExZFx1Yzc1OCBcdWM1OTEgXHVjNjA2XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWNlZjVcdWQ2NDBcdWIzNTRcdWM1ZDBcdWI5Y2MgXHVjZWY1XHVjNzQ0IFx1YWY0Mlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5TXHViMjk0IFx1Yzc3Y1x1YmMxOCBcdWM4OGNcdWMxMWQsIExcdWM3NDAgXHVjZWU0XHVkNTBjXHVjMTFkXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YmE3MCwgTFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHViNDUwXHVhYzFjXHVjNTI5IFx1YzMwZFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWM4OGNcdWMxMWRcdWM3NTggXHViYzMwXHVjZTU4XHVhYzAwIFNMTExMU1NMTFx1Yzc3Y1x1YjU0YywgXHVjZWY1XHVkNjQwXHViMzU0XHViOTdjICpcdWI4NWMgXHVkNDVjXHVjMmRjXHVkNTU4XHViYTc0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmUgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHJcbipTKkxMKkxMKlMqUypMTCo8XC9wcmU+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVjNjA4XHVjNWQwXHVjMTFjIFx1YzgwMVx1YzViNFx1YjNjNCBcdWI0NTAgXHViYTg1XHVjNzQwIFx1Y2VmNVx1ZDY0MFx1YjM1NFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODhjXHVjMTFkXHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgNTApIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODhjXHVjMTFkXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZWY1XHVjNzQ0IFx1Y2VmNVx1ZDY0MFx1YjM1NFx1YzVkMCBcdWIxOTNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjgxMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktJTk8iLCJkZXNjcmlwdGlvbiI6IjxwPk5ldyB0aGVhdGVyIGp1c3Qgb3BlbmVkIGluIE1pcmtvJnJzcXVvO3MgaG9tZSB0b3duLCBhbmQgTWlya28gYW5kIFNsYXZrbyBuYXR1cmFsbHkgd2VudCB0byBjaGVjayBpdCBvdXQuIE9wZW5pbmcgcHJvamVjdGlvbiB3YXMgZmlsbGVkIHRvIHRoZSBsYXN0IHBsYWNlLCBhbmQgTWlya28gZ290IG1hZCBiZWNhdXNlIGN1cC1ob2xkZXJzIGF0IGJvdGggc2lkZXMgb2YgaGlzIHNlYXQgd2VyZSB0YWtlbiBhbmQgaGUgaGFkIG5vd2hlcmUgdG8gcHV0IGhpcyBDb2tlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIHJvdyBpbiB0aGVhdGVyIGhhcyBOIHNlYXRzLiBUaGVyZSBpcyBhIHNpbmdsZSBjdXAtaG9sZGVyIGJldHdlZW4gYWRqYWNlbnQgc2VhdHMsIGFuZCBhbHNvIHR3byBhZGRpdGlvbmFsIGN1cC1ob2xkZXJzIGF0IGJvdGggZW5kcyBvZiB0aGUgcm93LiBFeGNlcHRpb24gdG8gdGhpcyBhcmUgcGFpcnMgb2YgbG92ZSBzZWF0cyAtIHRoZXJlIGlzIG5vIGN1cC1ob2xkZXIgYmV0d2VlbiB0aGVtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gaGVscCBNaXJrby4gR2l2ZW4gc2VxdWVuY2Ugb2YgbGV0dGVycyBkZXNjcmliaW5nIHNlYXRzIGluIHNvbWUgcm93LCBhbmQgYXNzdW1pbmcgdGhhdCBhbGwgc2VhdHMgYXJlIHRha2VuLCBmaW5kIHRoZSBtYXhpbXVtIG51bWJlciBvZiBwZW9wbGUgdGhhdCBjYW4gcHV0IHRoZWlyIGN1cHMgaW4gYSBjdXAtaG9sZGVyIHJpZ2h0IG5leHQgdG8gdGhlaXIgc2VhdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGV0dGVyICZsc3F1bztTJnJzcXVvOyBpbiB0aGUgc2VxdWVuY2UgZGVub3RlcyBvcmRpbmFyeSBzZWF0LCBhbmQgJmxzcXVvO0wmcnNxdW87IGRlbm90ZXMgbG92ZSBzZWF0LiBMb3ZlIHNlYXRzIHdpbGwgYWx3YXlzIGNvbWUgaW4gcGFpcnMgb2YgYWRqYWNlbnQgc2VhdHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkRpYWdyYW0gYmVsb3cgY29ycmVzcG9uZHMgdG8gc2VxdWVuY2UgJmxzcXVvO1NMTExMU1NMTCZyc3F1bzssIHdpdGggYXN0ZXJpeGVzIGRlbm90aW5nIGN1cC1ob2xkZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4qIFMgKiBMIEwgKiBMIEwgKiBTICogUyAqIEwgTCAqJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIGV4YW1wbGUsIGF0IGxlYXN0IHR3byBwZXJzb25zIHdvbiZyc3F1bzt0IGJlIGFibGUgdG8gcHV0IHRoZWlyIGN1cHMgaW50byBjdXAtaG9sZGVycy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgNTApLCBudW1iZXIgb2Ygc2VhdHMgaW4gYSByb3cuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgbGluZSBjb250YWlucyBhIHNlcXVlbmNlIG9mIE4gbGV0dGVycyAmbHNxdW87TCZyc3F1bzsgb3IgJmxzcXVvO1MmcnNxdW87LCBkZXNjcmliaW5nIHRoZSByb3cgYXMgc3RhdGVkIGFib3ZlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbWF4aW11bSBudW1iZXIgb2YgcGVvcGxlIHRoYXQgY2FuIHB1dCB0aGVpciBjdXBzIGluIGN1cC1ob2xkZXIgcmlnaHQgbmV4dCB0byB0aGVtLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #4 1번