사용자 도구

사이트 도구


ps:problems:boj:21757

나누기

ps
링크acmicpc.net/…
출처BOJ
문제 번호21757
문제명나누기
레벨골드 3
분류

DP

시간복잡도O(n)
인풋사이즈n<100,000
사용한 언어Python
제출기록42028KB / 112ms
최고기록112ms
해결날짜2022/02/13

풀이

  • 우선 당연하게도, 수열의 합이 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)

코드

"""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()

토론

댓글을 입력하세요:
W V V I O
 
ps/problems/boj/21757.txt · 마지막으로 수정됨: 2022/02/13 05:36 저자 teferi