Python 17제] 2021년 한국정보올림피아드 1차대회 초등부 2. 나누기

문제]

N개의 정수 수열 A1, A2,..., AN이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또 각 부분의 합은 모두 같아야 한다. 즉 어떤 i, j, k(1≤i＜j＜k＜N)에 대해서 [A1,...,Ai], [Ai+1,...,Aj], [Aj+1,...Ak], [Ak+1,...AN]으로 나눈다.

 

예를 들어 주어진 수열이 4, -1, 2, 1, -3, 1, 2, 2, 1, 3이라고 하자. 

이 수열을 아래과 같이 나누면 각 부분의 합이 달라서 허용되는 형태가 아니다.
[4, -1, 2], [1, -3, 1, 2], [2, 1], [3]
아래와 같이 나눈 경우 각 부분의 합이 모두 같다.
[4, -1], [2, 1],[-3, 1, 2, 2, 1], [3]
아래과 같이 나눈 경우들도 각 부분의 합이 모두 같다.
[4, -1], [2, 1, -3, 1, 2], [2, 1], [3]
혹은 [4, -1, 2, 1, -3], [1, 2], [2, 1], [3]
수열을 입력 받아 위와 같이 나눌 수 있는 가능한 방법의 개수를 계산하는 프로그램을 작성하라.

제약 조건]
▶ 4 ≤ N ≤ 100000
▶ 1 ≤ i ≤ N에 대해 -1000 ≤ Ai ≤ 1000


입력 형식]
첫 번째 줄에 수열의 길이 N이 주어진다.
두 번째 줄에 N개의 정수 A1, A2, ... ,AN이 공배 하나씩을 사이로 두고 주어진다.

출력 형식]
첫 번째 줄에 가능한 방법의 개수를 출력한다.
출력값이 매우 클 수 있으므로 C, C++ 언어에서는 long long형의 변수를, Java에서는 long형의 변수를 사용해야 한다.


입력 예제1]
4
1 1 1 1

출력 예제1]
1


입력 예제2]
10
4 -1 2 1 -3 1 2 2 1 3

출력 예제2]
3

 

 

출처]

2021년 한국정보올림피아드 1차대회 2교시 초등부pdf

 

 

참고풀이]

import sys #exit()

N = int(input())
if 4<=N<=100000:
    A = list(map(int,input().split()))
    for su in A:
        #1~N개의 수열중 -1000<=Ai<=1000 범위의 
        #수가 아니면 작업을 멈춘다.
        if su<-1000 or su >1000:
            sys.exit()
    #주어진 수열의 전체 합을 구한다.
    S = sum(A)
    dp = [1,0,0,0] #최소 1가지는 있다.
    ps = 0 #각부분의 공통합을 구하기 위하여 초기값을 0으로 셋팅
    #수열을 0~8까지 반복한다.
    for x in A[:-1]:
        ps += x #각 원소의 합을 구한다
        for i in [3,2,1]:
            if ps == S * i / 4:
                dp[i] += dp[i-1]

#합이 같은 가지수를 출력
print(dp[3])

 

 

출처]

이미지 : 독도전경

 

 

참고풀이 결과]

 

 

 

대한민국의 아름다운 영토, 독도의 봄