[백준] 1806. 부분합 (복습)

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

골드4 부분합, 투포인터 문제입니다

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 9876543210;
int n, s, m, x, l, r, ans = INF;
int a[100001];
int main() {
	FAST;
	cin >> n >> m;
	int sum = 0;
	REP(i, n) {
    //부분합에서 중요한건 첫번째 배열의 합이 0이 되어야한다는것 $$!!!
		cin >> x;
		sum += x;
		a[i] = sum;
	}
	
	rep(l, n) {
    //왼쪽 포인터는 오른쪽으로 1회 전진, 오른쪽 포인터도 1회 전진을 바꿔가면서 반복할 예정
		while (a[r] - a[l] < m && r <= n)r++;
		if (a[r]-a[l] >= m) {
			ans = min(ans, r - l);
		}
	}
    //갱신되지 않았으면 0을 출력
	ans == INF ? cout << 0 : cout << ans;

}

 

매우 매우 중요한 것은, 부분합 문제에서 첫번째 배열의 값은 0이라는 것이다 !

 

부분합의 두 지점의 차(왼쪽 포인터와 오른쪽 포인터)는 멀어질 수록 자동으로 점 점 점 커진다.

따라서 왼쪽 포인터를 고정시켰을 때, 일단 오른쪽 포인터를 계속 이동시키다가 s보다 커지는 부분부터는 더 옮길 이유가 없다는것

 

따라서 그 지점부터 왼쪽 포인터를 다시 오른쪽으로 한칸옮기고, 오른쪽포인터를 다시 움직인다. 이를 반복

rep(left_pointer,n){

    while(right_pointer<=n && a[right_pointer]-a[left_pointer]<s) right_pointer ++

}

만약 right_poitner가 범위 내에 있지만, 차이가 s보다 작다면 오른쪽 포인터를 오른쪽으로 한칸 옮겨준다.

 

복습 완 ! 

#include<bits/stdc++.h>

using namespace std;
int psum[100001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	psum[0] = 0;
	int n, s, x, sum = 0, ans = INT_MAX;
	cin >> n >> s;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		psum[i] = sum += x;
	}
	int le = 0, ri = 0;
	while (1) {
		if (ri>n)
			break;
		if (psum[ri] - psum[le] >= s) {
			ans = min(ans,ri - le);
			le++;
		}
		else
			ri++;
	}
	if (ans == INT_MAX)cout << 0;
	else
		cout << ans;
}

자료형 의 최대,최솟값을 저장하려면 

#include <limits.h> 

 

  	char num1 = CHAR_MIN;          // char의 최솟값
    short num2 = SHRT_MIN;         // short의 최솟값
    int num3 = INT_MIN;            // int의 최솟값
    long num4 = LONG_MIN;          // long의 최솟값
    long long num5 = LLONG_MIN;    // long long의 최솟값
    
    //TYPE_MAX; //자료형type의 최댓값 EX) INT_MAX