[BOJ | Python] 11059번: 크리 문자열

https://www.acmicpc.net/problem/11059

 

문제

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

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

예를 들어 S = "67896789" 인 경우에 정답은 "67896789"이 된다. 또, S = "6789789" 인 경우에 정답은 "789789"가 된다. S = "6789678" 인 경우에 정답은 "9678" 이다.

 

 

입력

첫째 줄에 문자열 S가 주어진다. S는 숫자로만 이루어져 있으며, 길이는 1,000을 넘지 않는다. 항상 크리 문자열이 존재하는 입력만 주어진다.

 

 

출력

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

 

 

풀이

S = input().strip()
N = len(S)
max_len = 0

for length in range(2, N + 1, 2):  # 짝수 길이만
    for i in range(N - length + 1):
        sub = S[i:i + length]
        mid = length // 2
        left = sum(map(int, sub[:mid]))
        right = sum(map(int, sub[mid:]))
        if left == right:
            max_len = max(max_len, length)

print(max_len)