정올 나누기

문제

예제

import sys
input = sys.stdin.readline
 
n = int(input())
arr = list(map(int, input().split()))
 
preSum = [0] * (n+1)
for i in range(1, n+1):
    preSum[i] = preSum[i-1] + arr[i-1]
 
ans = 0
 
if preSum[n] % 4 == 0:
    partial_sum = preSum[n] // 4
    dp = [[0]*4 for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        dp[i][0] = 1
        for j in range(1, 4):
            dp[i][j] = dp[i-1][j]
            if preSum[i] == partial_sum * j: 
                dp[i][j] += dp[i-1][j-1]
    ans = dp[n-1][3]
print(ans)

 

n: 배열 길이

arr: 수열

 

preSum[i]: arr[0]부터 arr[i-1]까지의 합

총합은 preSum[n]

 

 

partial_sum: 각 구간이 가져야 할 합

dp[i][j]: i번째 인덱스까지 고려했을 때, j개의 구간 경계가 성립하는 경우의 수

 

 

preSum[i] == partial_sum * j: 현재 위치까지의 누적합이 정확히 j번째 구간이 끝날 위치일 경우

그때는 이전 구간(j-1)까지 나눴던 경우의 수를 더함

 

 

n-1까지 고려했을 때, 3개의 경계가 만들어졌다면 → 4개의 구간으로 나뉜 것

결과를 출력