[백준] 1806번: 부분합
2021. 1. 28. 15:38ㆍAlgorithm/백준
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 |