백준 1806 - 부분합(C++)

문제 링크입니다.  https://www.acmicpc.net/problem/1806

1806번: 부분합

기본적인 두 포인터 알고리즘 문제였습니다.

문제 조건

출력 예시

 

S이상 합을 가질 수 있는 수열의 길이를 구하는 문제였습니다.

low 와 high를 정한뒤, low ~ high까지 vector의 합을 구한 다음, S와 비교한 뒤, 값에 따라 low 와 high를 증가하면 됩니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N;
int S;
int ans = 100001;
vector<int> number;

void solve() {
	int low = 0;
	int high = 0;
	int sum = number[0];
	while (low <= high && high < number.size()) {
		if (sum < S) {
			if (high < number.size() - 1) {
				high++;
				sum += number[high];
			}
			else break;
		}
		else if (sum == S) {
			ans = min(ans, high - low + 1);
			sum -= number[low];
			low++;		
		}
		else {
			ans = min(ans, high - low + 1);
			sum -= number[low];
			low++;
		}
	}
	if (ans == 100001) {
		cout << "0";
	}
	else cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		number.push_back(num);
	}
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요!