루미 알고리즘

#1318골드Going to School

PO 2013 결선코딩영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPoint valueConstraints
140There are at most 20 crossing streets
260No additional constraints.

예제

예제 1

입력
SNBNNSB
출력
4

예제 2

입력
SBSNNBSNNSSSNNNB
출력
8

출처 표기

출처: Programmeringsolympiaden 2013년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.