문제 분류 수업 진도 대회 채점현황 순위 질문게시판
게임
스도쿠 타이핑 리듬 타자게임 타이핑 테트리스 타이핑 인베이더 타이핑 지뢰찾기 8192 공룡게임 타이핑 플래피버드 랭킹
로그인

3186 : 수들의 합 (두 포인터)

•시간제한: 1.000 S •메모리제한: 256 MB •제출: 2 •통과: 2 •만든사람: suakii

3186 : 수들의 합 (두 포인터)

시간 1.000s · 메모리 256MB · 제출 2 · 정답 2
코드제출 문제 풀기
채점기록 통계 묻고답하기
이전 문제다음 문제

문제 설명

N개의 자연수로 이루어진 수열에서, 연속된 부분 수열의 합이 S가 되는 경우의 수를 구하세요.

두 포인터(Two Pointer) 기법: 왼쪽 포인터 L과 오른쪽 포인터 R로 현재 구간의 합을 조절합니다.

  • 합 < S → R을 오른쪽으로 이동 (구간 확장)
  • 합 > S → L을 오른쪽으로 이동 (구간 축소)
  • 합 = S → 경우의 수 +1, 이후 L 이동 계속
두 포인터 동작 예시 (배열: 1 2 3 4 2 5 3 1 1 2, S = 5) 0 1 2 3 4 5 6 7 8 9 ① 시작 1 2 3 4 2 5 3 1 1 2 L R 합(1) < 5 → R 오른쪽으로 ▶ ② R=2 1 2 3 4 2 5 3 1 1 2 L R 합(6) > 5 → L 오른쪽으로 ▶ ③ 정답! 1 2 3 4 2 5 3 1 1 2 L R 합(5) = 5 ✓ count = 1 ④ 정답! 1 2 3 4 2 5 3 1 1 2 L R 합(5) = 5 ✓ count = 2 ⑤ 정답! 1 2 3 4 2 5 3 1 1 2 L R 합(5) = 5 ✓ count = 3
[제약 조건]
• 1 ≤ N ≤ 100,000
• 1 ≤ S ≤ 1,000,000,000 (10억)
• 1 ≤ 각 자연수 ≤ 10,000
• 입력되는 모든 값은 자연수

입력 설명

첫째 줄에 N과 S가 공백으로 구분되어 주어집니다.
둘째 줄에 N개의 자연수가 공백으로 구분되어 주어집니다.

출력 설명

경우의 수를 출력하세요.

입력 예시
COPY
복사되었습니다!

10 5
1 2 3 4 2 5 3 1 1 2

출력 예시
COPY
복사되었습니다!

3

도움

(1,2,2), (5), (4,1) → 3가지

출처/분류

수학창의문제
BFStudy OJ is powered by HUSTOJ, Theme by suakii
개인정보처리방침
NOTICE  —  BFStudy OJ 정보샘
애들아, 문제 많이 풀고 게임 잠깐 하는거지?
— 정보샘