테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 나누기 ======

===== 풀이 =====
  * 우선 당연하게도, 수열의 합이 4의 배수가 아니라면 4조각으로 나누는 것이 불가능하니 그것부터 체크하자.
  * 합을 4로 나눈 값이 q라고 하자. A의 누적합 배열을 P라고 한다면(P[i] = A[1]+..+A[i]), 이 문제는 P[i]=q, P[j]=2*q, P[k]=3*q 이고 1≤i<j<k<N 인 (i,j,k)의 갯수를 찾는 것과 같다. DP를 이용해서 A[1]...A[x]까지에서의 i, (i,j), (i,j,k)의 갯수를 각각 유지하고, x를 증가시키면서 갱신하면 된다.
    * 갱신 순서에 살짝 주의가 필요하다. 잘못하면 q가 0일 경우를 제대로 처리하지 못할수도 있다.
  * 시간복잡도는 O(n) 


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 21757. 나누기".

- Problem link: https://www.acmicpc.net/problem/21757
- Solution link: http://www.teferi.net/ps/problems/boj/21757
"""


def main():
    N = int(input())  # pylint: disable=unused-variable
    A = [int(x) for x in input().split()]

    q, r = divmod(sum(A), 4)
    if r != 0:
        print('0')
        return
    q1, q2, q3 = q, q * 2, q * 3
    q1_count = q2_count = q3_count = 0
    s = 0
    for a_i in A[:-1]:
        s += a_i
        if s == q3:
            q3_count += q2_count
        if s == q2:
            q2_count += q1_count
        if s == q1:
            q1_count += 1

    print(q3_count)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_3}}