![]()
풀이 누적합과 투포인터를 이용한다. 왼쪽 포인터와 오른쪽 포인터를 설정하여 구간의 합을 계산한다. 구간의 합이 M과 같으면 경우의 수를 증가시키고 M보다 작으면 오른쪽 포인터를 증가시켜 구간을 확장하고 구간 합이 M보다 크면 왼쪽 포인터를 증가시켜 구간을 축소시킨다. 오른쪽 포인터가 끝에 도달할 때까지 반복한다. 시간복잡도 O(N) 코드 #include #include using namespace std; int main() { int N, M; cin >> N >> M; vector A(N); for (int i = 0; i > A[i]; } int count = 0; int left = 0; int right = 0; int sum = A[0]; while (right ..
![]()
문제 풀이 투 포인터 문제 start, end 두개의 포인터를 조작해서 구현한다. 두 수의 차가 원하는 결과보다 작다면 end를 증가시킨다(큰 수가 증가된다) 두 수를 비교하여 값의 차이를 이용해 답을 도출한다. 문제 코드 #include #include using namespace std; int n, m; int a[100005]; int mn = 0x7fffffff; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 0; i > a[i]; sort(a, a+n); int en = 0; for(int st = 0; st < n; st++){ while(en < n && a[en] - a[..
