메뉴 건너뛰기

문제

00c13 1학년 0  

시간메모리제출 올바른 답 비율
1초64MB
116
26
22.4%


나의 횟수나의 최근 판정시도 성공 비율
3021
70.0%
1학년 

홍길동은 초등학교 1학년이다. 길동이는 덧셈과 뺄셈을 좋아해서 여러 개의 숫자가 줄지어 있는 것(이하 숫자열)을 보면 마지막 두 숫자 사이에 = 를 넣고 나머지 숫자 사이에는 +, 또는 - 를 넣어 등식을 만드는 것이 취미다. 예를 들어 8 3 2 4 8 7 2 4 0 8 8 에서 등식 8 + 3 – 2 - 4 + 8 – 7 – 2 – 4 - 0 + 8 = 8 을 만든다.

길동이는 이러한 등식을 만든 다음 이 등식이 올바른지 확인하고 싶다. 그런데, 음수를 잘 모르고 20 이상의 숫자를 계산하지 못한다. 따라서 왼쪽부터 계산할 때 계산 도중에 나타나는 수가 0 이상 20 이하이어야 수식이 올바른지 확인할 수 있다. 예를 들어 8 + 3 – 2 – 4 – 8 - 7 + 2 + 4 + 0 + 8 = 8 은 올바른 수식이지만, 도중에 나타나는 8 + 3 – 2 – 4 – 8 가 음수이므로 길동은 이 수식이 올바른지 확인할 수 없다.

주어진 숫자열에 대해 길동이가 만들고 확인할 수 있는 올바른 등식의 개수를 구하는 프로그램을 작성하시오.

입력

입력 데이터는 2줄로 구성된다. 1번째 줄에는 숫자의 개수를 나타내는 정수 N(3 <= N <= 100)이 주어진다. 2번째 줄에는 0 이상 9 이하의 정수 N개가 공백을 사이에 두고 주어진다.

주어진 입력 데이터의 60%는 길동이가 만들고 확인할 수 있는 올바른 수식의 개수가 231-1을 초과하지 않으며, 어떤 경우에도 올바른 수식의 개수가 263-1을 초과하지 않는다.

출력

길동이가 만들고 확인할 수 있는 올바른 수식의 개수를 1번째 줄에 출력한다.

※ 예시 1에서 다음의 수식을 만들고 확인할 수 있기 때문에 10이다.

8 + 3 – 2 - 4 + 8 – 7 – 2 – 4 - 0 + 8 = 8
8 + 3 – 2 – 4 + 8 – 7 – 2 - 4 + 0 + 8 = 8
8 + 3 + 2 + 4 – 8 - 7 + 2 – 4 - 0 + 8 = 8
8 + 3 + 2 + 4 – 8 - 7 + 2 - 4 + 0 + 8 = 8
8 + 3 – 2 - 4 + 8 - 7 + 2 + 4 – 0 - 8 = 8
8 + 3 – 2 - 4 + 8 - 7 + 2 + 4 + 0 - 8 = 8
8 – 3 + 2 + 4 - 8 + 7 + 2 + 4 – 0 - 8 = 8
8 - 3 + 2 + 4 - 8 + 7 + 2 + 4 + 0 - 8 = 8
8 - 3 + 2 - 4 + 8 + 7 + 2 – 4 – 0 - 8 = 8
8 - 3 + 2 - 4 + 8 + 7 + 2 - 4 + 0 - 8 = 8

※ 예시 2에서 처럼 출력 값이 32bit 부호 있는 정수의 범위를 초과함을 유의하시오.

예시
1입력
11
8 3 2 4 8 7 2 4 0 8 8
출력
10
2입력
40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1
출력
7069052760
위로