[백준 1806번 C/C++] 부분합

 

[백준 1806번 C/C++] 부분합

 

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

1806번: 부분합

---

 

해결방안

 

투 포인터

누적합

---

 

처음 시도한 코드 - 시간초과

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, s; // n: 수열의 길이, s: 수열의 부분합 최소값

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

	cin >> n >> s;
	vector<int> v(n);
	for(int i=0; i<n; i++){
		cin >> v[i];
	}

	vector<int> result;
	int left = 0;
	int right = 1;
	int sumNum = v[left];
	while (left < n - 1)
	{
		if (right > n - 1) break;
		
		if (sumNum < s){
			sumNum += v[right];
			right++;
		}
		else if (sumNum >= s){
			result.push_back(right-left);
			sumNum = 0;

			left++;

			if (v[left] >= s)
			{
				result.push_back(1);
				cout << "1\n";
				return 0;
			}

			sumNum += v[left];
			right = left + 1;
		}
	}

	if (result.size() == 0) 
		cout << "0\n";
	else{
		sort(result.begin(), result.end());
		cout << result[0] << "\n";
	}
	
	return 0;
}

 

 

---

 

정답 코드 - 누적합 Ver.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, s; // n: 수열의 길이, s: 수열의 부분합 최소값
vector<int> result;

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

	cin >> n >> s;
	vector<int> v(n);
	int front = 0;
	int sumNum = 0;
	for(int i=0; i<n; i++){
		cin >> v[i];

		sumNum += v[i];

		while (sumNum >= s)
		{
			result.push_back(i - front + 1);
			sumNum -= v[front];
			front++;
		}		
	}

	if (result.size() == 0)
		cout << "0\n";
	else {
		sort(result.begin(), result.end());
		cout << result[0] << "\n";
	}
	
	return 0;
}

 

입력과 동시에 누적합이 시행되도록 코드를 수정하였다. 

 

 

---

 

다른 풀이 -  투 포인터 Ver.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

int n, s;

int main()
{
	cin >> n >> s;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];

	int left = 0, right = 0;
	int sumNum = 0, minLen = INT_MAX;
	while (left <= right) 
	{
		if (sumNum >= s)
		{
			minLen = min(minLen, right - left); // 가장 짧은 길이로 업데이트
			sumNum -= v[left];
            left++;
		}
		else if (right == n) 
			break;
		else {
			sumNum += v[right];
            right++;
        }
	}

	if (minLen == INT_MAX)
		cout << 0 << "\n";	
	else 
		cout << minLen << "\n";

	return 0;
}