크리 문자열

면접 대비

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

요약

숫자로 이루어진 문자열에서 앞뒤 절반의 자릿수 합이 같은 가장 긴 짝수 길이 부분 문자열의 길이를 구합니다.

난이도: 쉬움10점 중 3점
유형: 누적 합, 완전 탐색
정답자: 아직 제출이 없습니다

문제

숫자로만 이루어진 문자열 $S$ 가 주어진다. $S$ 의 연속한 부분 문자열 중 길이가 짝수이고 앞쪽 절반의 숫자 합과 뒤쪽 절반의 숫자 합이 같은 것을 크리 문자열이라고 한다. 빈 문자열은 크리 문자열이 아니다.

$S$ 의 크리 문자열 중 가장 긴 것을 찾는 프로그램을 작성하시오.

예를 들어 $S$ = 67896789이면 문자열 전체가 크리 문자열이다. 앞 절반 6789의 합이 30이고 뒤 절반 6789의 합도 30이기 때문이다. $S$ = 6789789이면 789789가 가장 긴 크리 문자열이고, $S$ = 6789678이면 9678이 가장 긴 크리 문자열이다.

입력

첫째 줄에 문자열 $S$ 가 주어진다. $S$ 는 숫자로만 이루어져 있고, 길이는 1,000 이하이다. 크리 문자열이 하나 이상 존재하는 입력만 주어진다.

출력

첫째 줄에 $S$ 의 크리 문자열 중 가장 긴 것의 길이를 출력한다.

예제6

예제 1
입력
```
67896789
```
예상 출력
```
8
```
예제 2
입력
```
6789789
```
예상 출력
```
6
```
예제 3
입력
```
6789678
```
예상 출력
```
4
```
예제 4
입력
```
11
```
예상 출력
```
2
```
예제 5
입력
```
1937
```
예상 출력
```
4
```
예제 6
입력
```
0000000
```
예상 출력
```
6
```