[210715][백준/BOJ] 1806번 부분합
문제
입출력
풀이
연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중에 가장 짧은 것의 길이를 구하는 문제이며 투포인터 알고리즘을 사용하면 된다.
15 이상인 수 중에 가장 짧은 것의 길이는 5+10, 10+7 인 2이다.
만약 이러한 합을 만드는 것이 불가능하다면 0을 출력하면된다.
- start와 end를 나타내는 두개의 포인터 s와 e를 0으로 초기화해준다.
- 두 포인터로 나타내는 합(e - s)이 n보다 크거나 같다면 s++를 해주며 길이를 구한다. 우리는 S보다 큰 값중에 최소인 길이를 찾아야 하므로 min함수를 통해 최소 길이를 구해준다. 또한 이러한 합을 만드는것이 불가능할때를 생각해야하므로 한번이라도 조건문이 실행됐는지를 bool형 변수 flag를 통해 파악한다.
- 두 포인터로 나타내는 합이 n보다 작으면 e++를 해준다.
- 합이 n보다 크거나 같지 않으면서 e가 배열의 끝에 도달할때까지 반복한다.
- flag가 true라면 조건문이 한번도 실행하지 않은것으로 0을 출력하며 false라면 ans를 출력한다.
코드
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, S;
cin >> n >> S;
vector<int> V(n);
for (int i = 0; i < n; ++i)
cin >> V[i];
int s = 0, e = 0, ans = n, sum = 0, idx;
bool flag = true;
while (true)
{
if (sum >= S)
{
sum -= V[s++];
idx = e - s + 1;
ans = min(ans, idx);
flag = false;
}
else if (e == n) break;
else sum += V[e++];
}
if (flag == true)
cout << 0 << '\n';
else
cout << ans << '\n';
}
Author And Source
이 문제에 관하여([210715][백준/BOJ] 1806번 부분합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kwkim95/210715백준BOJ-1806번-부분합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)