[python/백준] 11059: 크리문자열

11059번: 크리 문자열

def main():

    s = list(input().strip())

    n = len(s)

    flag = 0

   

    dp = [0]* n

    dp[0] = int(s[0])

    for i in range(1,n):

        dp[i] = dp[i-1]+int(s[i])

    # print(dp)

    if n % 2 > 0 : n-=1

    while n>0:

        for i in range(len(s)-n+1):

            x = n //2 +i # 절반이 존재하는 위치. 8자리면 4. x-1과 x사이가 절반이겟지...

            # print(x,i,n)

            # print(dp[x-1] ,dp[n+i-1]-dp[x-1])

           

           if dp[x]-dp[i] == dp[n+i]-dp[x]:

                flag = 1

                break

        if flag ==1:

            break

        n -= 2

    print(n)

누적합을 사용하여 문제를 풀 수 있다.