챔퍼노운 부분수열

시간 제한2초메모리 제한2048 MB

요약

숫자 문자열이 1부터 k까지 정수를 이어 붙인 문자열의 부분 수열이 되는 가장 작은 k를 구합니다.

문제

$k$ 번째 Champernowne 단어는 양의 정수 1부터 $k$ 까지를 차례로 이어 붙여 쓴 문자열이다. 예를 들어 $10$ 번째 Champernowne 단어는 $12345678910$ 이다.

어떤 유한한 숫자 문자열이든, 그 문자열이 어떤 $k$ 번째 Champernowne 단어의 부분수열로 나타나는 정수 $k$ 가 존재한다.

문자열 $s$ 가 문자열 $t$ 의 부분수열이라는 것은, $t$ 에서 문자 몇 개(0개도 가능)를 지워 $s$ 를 만들 수 있다는 뜻이다.

주어진 숫자 문자열이 $k$ 번째 Champernowne 단어의 부분수열이 되는 가장 작은 정수 $k$ 를 구하라.

첫 줄에 문자열의 길이를 나타내는 정수 $n$ $(1 \leq n \leq 10^5)$ 이 주어진다. 둘째 줄에는 길이가 $n$ 인 숫자 문자열이 주어진다.

주어진 문자열이 부분수열이 되는 가장 작은 정수 $k$ 를 출력한다.