마법 서판
실버 I의견: 0
마법 왕국의 기록관이 \(N\)개의 정수가 적힌 서판을 발견했다. 서판에는 양수, 음수, \(0\)이 모두 적혀 있을 수 있다.
기록관은 연속된 구간의 합이 정확히 \(K\)인 구간이 몇 개인지 알고 싶어한다. 연속 부분 배열이란 서판에서 연속으로 이어진 하나 이상의 원소로 이루어진 구간이다. 서로 다른 두 구간이 같은 원소들로 이루어지더라도, 시작 혹은 끝 위치가 다르면 다른 구간으로 센다.
조건을 만족하는 연속 부분 배열의 수를 구하여라.
- \(1 \le N \le 100\,000\)
- \(-10^9 \le K \le 10^9\)
- 서판의 각 정수는 \(-100\) 이상 \(100\) 이하이다.
첫째 줄에 정수의 개수 \(N\)과 목표 합 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 서판에 적힌 \(N\)개의 정수가 공백으로 구분되어 주어진다.
합이 정확히 \(K\)인 연속 부분 배열의 수를 출력한다.
5 4
1 2 3 -1 2
2
합이 \(4\)인 연속 부분 배열을 구간으로 나타내면 인덱스 \((1, 3)\)의 \(2+3-1=4\)와 인덱스 \((2, 4)\)의 \(3-1+2=4\)로 총 \(2\)개이다.
3 2
1 1 1
2
합이 \(2\)인 연속 부분 배열은 \([1,1]\)이 인덱스 \((0,1)\)과 \((1,2)\) 두 곳에 등장하므로 답은 \(2\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
마법 서판
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 서판