433 단어
2 분
백준 1806번 C++ 풀이

문제#

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력#

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

출력#

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

아이디어#

합을 이용한 문제이니 부분합을 이용하고 구간만 필요하니 투 포인터를 이용해서 부분합 배열을 검사해 내가며 길이가 가장 짧은 것을 찾는걸 생각했다.

이 경우 부분합 배열을 모두 탐색해야하므로 O(N)O(N)의 시간 복잡도를 가져 제한시간과 숫자 범위를 고려할 때 성공할 만하다고 결론지었다.

코드#

#include <cmath>
#include <iostream>
#include <numeric>
using namespace std;
constexpr int INF = numeric_limits<int>::max();
int N, S;
int arr[100001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> S;
for (int i = 1; i <= N; ++i)
{
cin >> arr[i];
arr[i] += arr[i - 1];
}
int len = INF;
int first = 1;
int second = 1;
while (second != N + 1)
{
int sum = arr[second] - arr[first - 1];
if (sum >= S)
{
len = second - first + 1 < len ? second - first + 1 : len;
first++;
}
else
second++;
}
cout << ((len != INF) ? len : 0);
}
결과

맞았습니다

깃헙링크 : link