대한민국을 지키는 가장 긴 힘

면접 대비

시간 제한1초메모리 제한1024 MB

요약

숫자 문자열을 1부터 641까지의 수로 나누되, 조각의 개수가 가장 적도록 나눌 때의 최소 개수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 동적 계획법, 문자열
정답자: 아직 제출이 없습니다

문제

대한민국 공군의 표어는 "대한민국을 지키는 가장 높은 힘"이다. 그러나 공군의 복무 기간은 $1$ 년 $9$ 개월로 현역 병사 중 가장 길다. 그래서 공군 병사들은 자조적으로 "대한민국을 지키는 가장 긴 힘"이라는 농담을 주고받는다.

오늘도 이 농담을 나누던 도훈이네 부대 병사들은 전역의 염원을 담은 전역일 페이퍼를 만들기로 했다. 전역일 페이퍼는 긴 종이에 병사들의 남은 복무 일수를 띄어쓰기 없이 한 줄로 적은 것이다. 예를 들어 남은 복무 일수가 각각 $124$ 일, $631$ 일, $2$ 일인 병사들이 순서대로 적으면, 종이에는 $1\,246\,312$ 가 적힌다. 공군의 최대 복무 일수는 $641$ 일이므로, 전역일 페이퍼에 남은 복무 일수를 적은 병사들은 모두 $1$ 이상 $641$ 이하의 수만 적었고, 수 앞에 불필요한 $0$ 은 붙이지 않았다.

이 전역일 페이퍼를 보던 도훈이는 거기에 자신의 남은 복무 일수를 적은 병사가 몇 명인지 궁금해졌다. 하지만 종이에 적힌 수만으로는 정확한 인원을 알 수 없다. 각 병사가 $1$ 이상 $641$ 이하의 수만 적었다는 조건에서, 전역일 페이퍼를 작성한 병사 수의 최솟값을 구하자.

입력

첫 번째 줄에 전역일 페이퍼에 적힌 수의 자릿수 $N$ 이 주어진다.

두 번째 줄에 전역일 페이퍼에 적힌 수를 나타내는 길이 $N$ 의 정수 $S$ 가 주어진다.

주어진 수 $S$ 가 전역일 페이퍼에 적힌 수가 될 수 있음이 보장된다.

출력

첫 번째 줄에 전역일 페이퍼를 작성한 병사 수의 최솟값을 출력한다.

제한

$1 \le N \le 5\,000$
모든 입력은 정수이다.

예제5

예제 1
입력
```
3
123
```
예상 출력
```
1
```
예제 2
입력
```
3
873
```
예상 출력
```
2
```
예제 3
입력
```
5
51324
```
예상 출력
```
2
```
예제 4
입력
```
6
560010
```
예상 출력
```
3
```
예제 5
입력
```
1
1
```
예상 출력
```
1
```