| 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 ※ 예시 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 | ||