728x90
시간 제한 : 0.5초
메모리 제한 : 128MB
입력
첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
출력
첫째 줄에 경우의 수를 출력한다.
소스코드
#include <iostream> #include <vector> using namespace std; int main(void) { int n, m, s, e, sum = 0, cnt = 0; cin >> n >> m; vector<int> arr(n); for (int i = 0; i < n; i++) cin >> arr[i]; s = 0, e = 0; while (1) { if (sum >= m) sum -= arr[e++]; else if (s == n) break; else sum += arr[s++]; if (sum == m) cnt++; } cout << cnt; }
Tip
투 포인터 알고리즘이라고 표현이 되어 있다. 슬라이딩 윈도우를 생각하고 문제를 풀면 되는 문제이다.
728x90
'Computer Science > Algorithm Problem' 카테고리의 다른 글
백준] 11728 - 배열 합치기 (0) | 2018.08.04 |
---|---|
백준] 2858 - 기숙사 바닥(COCI 2010/2011) (0) | 2018.08.03 |
백준] 14697 - 방 배정하기(KOI 2017 전국 - 초등부, 중등부) (0) | 2018.07.29 |
백준] 1018 - 체스판 다시 칠하기 (0) | 2018.07.28 |
백준] 14563 - 완전수(중앙대학교 CodeRace 2017) (0) | 2018.07.27 |