식별자 수열
시간 제한7초메모리 제한128 MB
숫자로 된 문자열을 여러 조각으로 나누되, 각 조각을 10진수로 읽은 값이 서로 달라야 합니다. 이런 분할에서 조각 개수의 최댓값을 구합니다.
문제
Johnny는 해커이며, 최근 한 대형 은행의 데이터베이스를 입수했다. 가장 중요한 작업은 여기서 고객 ID를 추출하는 것이다. ID는 정렬된 뒤 하나의 숫자열로 이어 붙여져 있으며, 어디에서 이어 붙였는지를 나타내는 표시는 없다. 그 표시는 별도의 파일에 들어 있는데, Johnny에게는 그 파일이 없다. Johnny는 숫자열을 여러 조각으로 잘라 얻을 수 있는 ID의 개수를 구하려 한다. Johnny는 운을 믿는다. 자르는 방법이 여러 가지라면 ID 개수를 최대로 만드는 방법이 맞을 것이라고 본다.
ID는 단계마다 따로 부여되었기 때문에 길이가 다를 수 있고 앞자리에 0이 올 수도 있다. 다만 Johnny는 각 ID를 10진수 위치 표기법의 수로 읽었을 때 값이 고유하다는 것을 알고 있다.
입력
입력의 첫 줄에만 개()의 10진수 숫자로 이루어진 수열이 주어진다. 숫자 사이에는 공백을 포함한 다른 문자가 없다. 이것이 Johnny가 가진 ID 수열이다.
출력
숫자열을 잘라서 만들 수 있는 고객 ID의 최대 개수를 자연수 하나로 출력한다.
힌트
답에 해당하는 ID 수열은 1, 05, 40, 910이다. ID 05의 수 값은 5이다.