합이 K인 연속 구간의 수
실버 III의견: 0
양치기 해나는 \(N\)마리의 양 떼를 일렬로 세웠다. \(i\)번째 칸에 있는 양의 수는 \(a_i\)이다. 양의 수는 음수일 수도 있다(양이 옆 칸으로 뛰어가 음수로 기록되기도 한다).
해나는 연속한 구간 \([l, r]\;(1 \le l \le r \le N)\)을 선택해 구간의 합이 정확히 \(K\)가 되는 경우의 수를 구하고 싶다.
조건을 만족하는 \((l, r)\) 쌍의 수를 출력하여라.
- \(1 \le N \le 100\,000\)
- \(-10^9 \le K \le 10^9\)
- \(-1\,000 \le a_i \le 1\,000\)
첫째 줄에 양 떼의 칸 수 \(N\)과 목표 합 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 각 칸의 양 수 \(a_1, a_2, \dots, a_N\)이 공백으로 구분되어 주어진다.
연속 구간의 합이 \(K\)인 \((l, r)\) 쌍의 수를 출력한다.
5 4
1 2 -1 3 2
2
합이 \(4\)인 연속 구간: \([1,3]\;(1+2-1+3=5\)? 아니요), 인덱스 1-3: \(1+2-1=2\), 인덱스 1-4: \(1+2-1+3=5\), 인덱스 2-4: \(2-1+3=4\) ✓, 인덱스 2-5: \(2-1+3+2=6\), 인덱스 4-5: \(3+2=5\), 인덱스 3-4: \(-1+3=2\), 인덱스 1-2: \(1+2=3\), 인덱스 5-5: \(2\). 합이 \(4\)인 구간은 \((2,4)\)와 \((1,5)\)의 \(2\)개이다.
5 2
1 1 1 1 1
4
길이 \(2\)인 구간이 \(4\)개 있으므로 합이 \(2\)인 구간의 수는 \(4\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
합이 K인 연속 구간의 수
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
합이 K인 연속 구간의 수