KOI 1차 2021 초2- 나누기 > 문제은행 : 정보올림피아드&알고리즘


4725 : 나누기

제한시간
1000 ms   
메모리제한
512 MB   
해결횟수
33 회   
시도횟수
156 회   

문제

N개의 정수 수열 A1, A2, ..., AN이 주어진다.

수열을 각각이 연속된 네 부분으로 나누려고 한다.

단, 각 부분은 최소 하나의 수를 포함해야 한다.

또, 각 부분의 합은 모두 같아야 한다.

즉, 어떤 i, j, k(1 ≤ i < j < k < N)에 대해서 [A1, ...Ai], [Ai+1, ... Aj], [Aj+1, ... Ak], A[k+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 ≤​ 100,000

* 모든 1 ≤ i ≤ N에 대해 -1,000 ≤​ Ai ≤​ 1,000

 

[부분 문제]

1.​ (5점) 모든​ 1 ≤ i ≤ N에 대해​  A​= 0

2. (7점) 모든​ 1 ≤ i ≤ N에 대해​  A​> 0​

3.​ (4점) 모든​ 1 ≤ i ≤ N에 대해​  A​≥ 0​

4.​ (11점)​ N ≤ 10​ 

5.​ (19점)​ N ≤ 500 

6.​ (23점) N ≤ 5,000 

7.​ (31점) 추가 제약 조건 없음

 


입력형식

첫 번째 줄에 수열의 길이 N이 주어진다.

두 번째 줄에 N개의 정수 A1, A2, ..., AN​이 공백 하나씩을 사이로 두고 주어진다.


출력형식

첫 번째 줄에 가능한 방법의 개수를 출력한다.

출력 값이 매우 클 수 있으므로 C, C++언어에서는 long long 형의 변수를, 
Java에서는 long형의 변수를 사용해야 한다.


입력 예

4
1 1 1 1

출력 예

1

입력 예

10
4 -1 2 1 -3 1 2 2 1 3

출력 예

3

데이타 만든사람 : ohjtgood

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP