Processing math: 100%
문제1683--나누기

1683: 나누기

[만든사람 : ]
시간제한 : 1.000 sec  메모리제한 : 512 MB  제출 : 21  맞은 사람 : 3

제출  

문제 설명

N개의 정수 수열 A1,A2,,AN이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어떤 i,j,k (1i<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]
수열을 입력 받아 위와 같이 나눌 수 있는 가능한 방법의 개수를 계산하는 프로그램을 작성하라.

입력 설명

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

출력 설명

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

입력 예시1 Copy

4
1 1 1 1

출력 예시1 Copy

1

입력 예시2 Copy

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

출력 예시2 Copy

3

출처/분류

C3coding