영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
Figure 1: The dotted line shows Cissi's optimal path in the first example.
Cissi is walking from her home to school, following a long street going from the west to the east. On her way, she passes a number of street crossings where the crossing street either goes north (N), south (S) or both (B). At every street crossing, there are crosswalks on both the crossing streets and the main street (see the figure above), and she can only cross the street on the crosswalks.
Her home is to the north of the main street, furthermost to the west. The school is to the north of the main street, furthermost to the east. Write a program that helps Cissi compute the smallest number of streets that she must cross on her path to school.
Input
The input contains a single line with at most 1000 letters, each of which is N, S or B. The letters describe the crossing streets exactly in the order Cissi will pass them on her way to school.
Output
A single line with an integer, the smallest number of streets Cissi needs to cross.
Scoring
Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.
| Group | Point value | Constraints |
|---|---|---|
| 1 | 40 | There are at most 20 crossing streets |
| 2 | 60 | No additional constraints. |
예제
예제 1
SNBNNSB
4
예제 2
SBSNNBSNNSSSNNNB
8