파일 삭제

면접 대비

시간 제한5초메모리 제한512 MB

요약

위쪽에 붙은 이름 상자들의 너비가 주어질 때, 'y' 파일은 모두 지우고 'n' 파일은 남기는 최소 선택 상자 개수를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 기하, 구간, 구현
정답자: 아직 제출이 없습니다

문제

파일 관리자는 폴더 하나의 내용을 창 하나에 보여 준다. 파일 이름은 폴더에 저장된 순서대로 한 줄에 하나씩 나열된다.

파일 이름은 각각 직사각형 안에 그려지고, 이 직사각형을 이름 상자라고 하자. 이름 상자는 모두 창의 왼쪽 변에 붙어 있다. 이름 상자의 높이는 1이고 너비는 파일 이름의 길이와 같다. 즉 $i$ 번째 파일의 이름 상자는 가로로 $0$ 부터 $L_i$ 까지, 세로로 목록 맨 위에서 아래로 잰 $i-1$ 부터 $i$ 까지를 차지한다. 아래 그림은 acm.in1, acm.c~, acm.c 세 파일을 이 순서로 저장한 폴더의 창이다.

그림 1

삭제는 두 단계로 이루어진다. 먼저 마우스를 끌어 직사각형 하나를 지정하고, 이 직사각형을 선택 상자라고 하자. 그다음 삭제 키를 누른다. 이름 상자가 선택 상자와 겹치는 파일만 지워진다. 삭제가 끝나면 파일 관리자는 남은 이름 상자를 위로 당겨 어느 상자 위에도 빈 자리가 없게 다시 쌓는다. 선택 상자는 어디에나 놓을 수 있고, 꼭짓점이 정수 좌표에 있을 필요는 없다.

그림 2처럼 지정하면 acm.in1과 acm.c~가 지워지고, 남은 acm.c는 그림 3처럼 창 맨 위로 올라온다.

그림 2

그림 3

폴더에 파일이 $N$ 개 있고, 그중 버릴 파일은 이미 정해 두었다. 정해 둔 파일을 모두 지우면서 나머지는 하나도 지우지 않으려면 삭제를 최소 몇 번 해야 하는지 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 하나로 이루어지고, 형식은 다음과 같다.

N
D1 L1
D2 L2
...
DN LN

첫째 줄에 폴더 안 파일 개수 $N$ 이 주어진다 ( $1 \le N \le 1000$ ). 다음 $N$ 개 줄에는 문자 $D_i$ 와 정수 $L_i$ 가 주어진다 ( $1 \le L_i \le 1000$ ). $D_i$ 가 y이면 $i$ 번째 파일은 지워야 하고, n이면 남겨야 한다. $L_i$ 는 $i$ 번째 파일 이름의 길이이다. 파일은 창에 나열되는 순서대로 주어진다.

출력

y로 표시한 파일을 모두 지우면서 n으로 표시한 파일은 모두 남기는 데 필요한 최소 삭제 횟수를 출력한다. y로 표시한 파일이 하나도 없으면 0을 출력한다.

예제3

예제 1
입력
```
3
y 7
y 6
n 5
```
예상 출력
```
1
```
예제 2
입력
```
3
y 7
n 6
y 5
```
예상 출력
```
2
```
예제 3
입력
```
6
y 4
n 5
y 4
y 6
n 3
y 6
```
예상 출력
```
2
```