원형 숫자열 나누기

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

요약

원형 숫자 문자열을 연속된 K개 부분으로 나누어 가장 큰 부분의 값을 가장 작게 만들고 그 값을 출력합니다.

문제

숫자 '1'부터 '9'까지로만 이루어진 길이 $N$ 의 원형 문자열이 주어진다. 이 문자열을 비어 있지 않은 연속한 $K$ 개의 조각으로 나눈다. 각 조각은 정수 하나의 십진 표기이다. 조각 가운데 최댓값이 가장 작아지도록 나누고, 그때의 최댓값을 구하라.

예를 들어 문자열이 7654321이고 $K = 3$ 이면 최적 분할은 {176, 54, 32}이고 최댓값은 176이다. 문자열은 원형이라 마지막 문자 다음에 첫 문자가 이어진다. 이 예의 176이 그렇게 만들어진 조각이다.

첫째 줄에 정수 $N$ 과 $K$ 가 주어진다. ( $3 \le N \le 100000$ , $2 \le K \le N$ ) 둘째 줄에 '1'부터 '9'까지의 문자로만 이루어진 길이 $N$ 의 문자열이 주어진다.

최적 분할의 최댓값을 출력한다.

문자열이 4321이고 $K = 2$ 이면 최적 분할은 {32, 14}이다. 문자열이 7654321이고 $K = 3$ 이면 {176, 54, 32}이다. 문자열이 12321이고 $K = 5$ 이면 분할이 하나뿐이라 {1, 2, 3, 2, 1}이 된다.