4062 : 연속 부분합이 K인 구간 개수
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 5
•통과: 3
•만든사람: suakii
문제 설명
$N$개의 정수로 이루어진 수열에서 연속된 부분 수열의 합이 정확히 $K$가 되는 구간의 개수를 구하는 프로그램을 작성하시오.
구간은 시작 인덱스 $i$와 끝 인덱스 $j$ ($i \le j$)로 결정된다.
[제약 조건]
• $1 \le N \le 100$
• $-10000 \le K \le 10000$
• $-100 \le (\text{수열의 각 정수}) \le 100$
• 입력되는 모든 값은 정수
구간은 시작 인덱스 $i$와 끝 인덱스 $j$ ($i \le j$)로 결정된다.
[제약 조건]
• $1 \le N \le 100$
• $-10000 \le K \le 10000$
• $-100 \le (\text{수열의 각 정수}) \le 100$
• 입력되는 모든 값은 정수
입력 설명
첫째 줄에 수열의 크기 $N$과 목표 합 $K$가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
출력 설명
조건을 만족하는 연속 부분합 구간의 개수를 출력한다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 5
1 2 3 4 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
이중 반복문으로 모든 구간 $[i, j]$ ($i \le j$)에 대해 합을 계산하고 $K$와 같으면 카운트한다.
시간 복잡도 $O(N^2)$ 또는 $O(N^3)$ 방식 모두 $N \le 100$에서는 통과한다.
시간 복잡도 $O(N^2)$ 또는 $O(N^3)$ 방식 모두 $N \le 100$에서는 통과한다.