[백준 11059] 크리 문자열 - 파이썬

문제

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

 

 

 

풀이

1. 문자열을 정수 배열로 변환한다.

2. 해당 배열의 누적 합을 새로운 배열에 추가한다.

3. 모든 짝수 길이의 부분 문자열을 탐색하며 절반의 합을 계산한다.

4. 만약 절반의 합이 서로 일치한다면 해당 문자열을 길이를 저장한다.

 

 

 

코드

def find(s):
    n = len(s) 
    ans = 0
    
    # 문자열을 정수 배열로 변환
    arr = [int(char) for char in s]
    
    # 누적 합 계산
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]
        
    
    # 모든 짝수 길이의 부분 문자열 탐색
    for length in range(2, n + 1, 2):
        for start in range(n - length + 1):
            mid = start + length // 2
            
            # 누적 합을 이용하여 각 절반의 합 계산
            sum_front = prefix_sum[mid] - prefix_sum[start]
            sum_back = prefix_sum[start + length] - prefix_sum[mid]
            
            if sum_front == sum_back:
                ans = max(ans, length)
                
    return ans
                
s = str(input())
print(find(s))