증가 수열

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

요약

긴 숫자 문자열을 공백으로 나눠 엄격히 증가하는 수열을 만들고, 마지막 수를 최소화한 뒤 앞의 수들을 차례로 최대화하는 분할을 찾아 전체 곱을 1,000,000,003으로 나눈 나머지를 구하는 문제입니다.

문제

지민이는 길이가 N인 큰 정수 하나를 가지고 있다.

이 정수의 자리 사이에 공백을 넣어 여러 정수로 나누려고 한다. 나누어진 정수들은 왼쪽에서 오른쪽으로 갈수록 엄격히 증가해야 한다. 같은 값은 사용할 수 없으며, 각 정수는 0으로 시작해도 된다.

가능한 나누기 방법이 여러 가지라면 마지막 정수의 값을 가장 작게 만든다. 그런 방법도 여러 가지라면 첫 번째 정수의 값을 가장 크게 하고, 그래도 같으면 두 번째 정수의 값을 가장 크게 하는 식으로 앞에서부터 차례대로 비교해 하나를 고른다.

선택된 증가 수열의 모든 원소를 곱한 뒤 1,000,000,003으로 나눈 나머지를 출력하라.

첫째 줄에 정수 하나가 주어진다. 길이는 최대 2500이고, 첫 자리는 0이 아니다.

선택된 수열의 원소를 모두 곱한 값을 1,000,000,003으로 나눈 나머지를 출력한다.

입력 20210222에서는 마지막 정수를 최소로 만드는 방법이 다음 네 가지이다.

첫 번째 원소를 비교하면 20으로 시작하는 두 방법만 남는다. 그다음 두 번째 원소를 비교하면 210이 21보다 크므로 선택되는 수열은 20 210 222이다.