같은 높이로 돌아오기
골드 V의견: 0
한 등산로가 일직선으로 뻗어 있고, \(N\)개의 구간으로 나뉘어 있다. \(i\)번째 구간을 한 번 지날 때마다 고도가 \(A_i\)만큼 변한다. \(A_i\)가 양수이면 그만큼 올라가고, 음수이면 그만큼 내려가며, \(0\)이면 고도가 그대로다.
연속한 구간들의 묶음 \([i, j]\ (1 \le i \le j \le N)\)를 고른 뒤 \(i\)번째 구간 입구에서 출발하여 \(j\)번째 구간 끝까지 걷는 것을 생각하자. 이때 도착 지점의 고도가 출발 지점의 고도와 정확히 같아지는, 즉
$$ A_i + A_{i+1} + \dots + A_j = 0 $$
을 만족하는 연속 구간 \([i, j]\)가 모두 몇 개인지 구하여라.
- \(1 \le N \le 100\,000\)
- \(-10^9 \le A_i \le 10^9 \ (1 \le i \le N)\)
- 입력으로 주어지는 모든 값은 정수이다.
첫째 줄에 정수 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.
고도 변화의 합이 \(0\)이 되는 연속 구간 \([i, j]\)의 개수를 한 줄에 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 30점 | \(1 \le N \le 2\,000\) |
Subtask 2 | 20점 | \(-1 \le A_i \le 1 \ (1 \le i \le N)\) |
Subtask 3 | 50점 | 추가 제한이 없다. |
6
3 -3 2 -2 -1 16고도 변화는 차례로 \(3, -3, 2, -2, -1, 1\)이다. 합이 \(0\)이 되는 연속 구간은
$$ [1,2],\ [3,4],\ [5,6],\ [1,4],\ [3,6],\ [1,6] $$
의 \(6\)개이다. 예를 들어 \([3,6]\)은 \(2 + (-2) + (-1) + 1 = 0\)이고, \([1,6]\)은 전체 합이 \(0\)이다.
4
1 0 -1 22고도 변화는 \(1, 0, -1, 2\)이다. 합이 \(0\)이 되는 구간은 두 번째 구간 하나만 고른 \([2,2]\)(고도 변화 \(0\))와, \(1 + 0 + (-1) = 0\)인 \([1,3]\)의 \(2\)개이다.
3
4 2 50모든 구간에서 고도가 오르기만 하므로, 합이 \(0\)이 되는 연속 구간은 존재하지 않는다.
rip 작성
출처 지정되지 않음
평가 및 의견
같은 높이로 돌아오기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
같은 높이로 돌아오기