[백준] 1806번: 부분합

2021. 1. 28. 15:38Algorithm/백준

 

1806번: 부분합

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

www.acmicpc.net

 

1)첫번째 풀이-시간초과

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

int solution(vector<int>arr,int s) {
	bool pos = false;
	vector<int>sum;
	vector<int>min;

	for (int i = 0;i < arr.size();i++) {
		if (sum.empty()) sum.push_back(arr[i]);
		else sum.push_back(sum[i-1] + arr[i]);
	}

	for (int i = 0;i < sum.size();i++) {
		for (int j = i;j < sum.size();j++) {
			if (i == j && s <=sum[i]) {
				pos = true;
				min.push_back(1);
			}
			else if (i < j&& s<=(sum[j] - sum[i])) {
				pos = true;
				min.push_back(j - i);
			}
		}
	}

	if (pos) return *min_element(min.begin(), min.end());
	return 0;
}

int main() {
	int n, s;
	vector<int>arr;
	
	cin >> n >> s;
	for (int i = 0,t=0;i < n;i++) {
		cin >> t;
		arr.push_back(t);
	}

	cout << solution(arr, s);
	return 0;
}

'Algorithm > 백준' 카테고리의 다른 글

[백준] 15649번: N과 M  (0) 2021.01.30
[백준] 1806번: 부분합  (0) 2021.01.29
[백준] 1759번: 암호만들기  (0) 2021.01.28
[백준] 6603번: 로또  (0) 2021.01.27
[백준] 1476번: 날짜계산  (0) 2021.01.27