백준 2003 수들의합2 c++ // 투포인터 정석풀이

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

1. 주의사항

v.push_back(0);

마지막에 0을넣어야 e++되면서 0을 가르킴 => out of index 방지

 

2. 전체코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, m,ret,temp;
vector<ll> v;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> temp;
		v.push_back(temp);
	}
	v.push_back(0);

	ll s = 0, e = 1, sum = v[0];
	while (1) {
		if (sum == m) ret++;
		if (sum <= m) sum += v[e++];	//e를 한칸뒤로
		if (sum > m)sum -= v[s++];	//s를 한칸뒤로
		if (e == v.size()) break;
	}
	cout << ret;
}

 

===========================================

* 2회독 25.1.25

 

* 투포 탈출조건 안헷갈리는법

• 애초에 st, en을 sum에 포함할건지 안할건지 정하고 들어가면된다.
• en이 불포함 => while ( en < = n) 까지 돌리면된다. // en이 n-1까지 sum이 계산되면 되므로.

• 일단암기..
• 해당 알고리즘으로 예시를 돌려보자

e가 n까지 가는게 특징

• 누적합 배열같은건 필요없다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,m,ret;
int arr[10000+4], sum[10000+4];

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   cin>>n>>m;
   for(int i=0;i<n;++i) {
      cin>>arr[i];
   }

   int st=0; // sum에 포함
   int en=1; //sum에 안포함 => while문 범위를 같은것까지 넣어야함.
   int sum=arr[st];

   while(en<=n) {
      //감소하는 수 필요
      if(sum==m) {
         ret++;
         sum-=arr[st];
         st++;   
      }
      if(sum>m) {
         sum-=arr[st];
         st++; 
      }
      //증가하는 수 필요
      if(sum<m) {
         sum+=arr[en];
         en++; 
      }
   }
   
   cout<<ret;

   return 0;
}