[백준 알고리즘] 1806번: 부분합
April 10, 2021
https://www.acmicpc.net/problem/1806
문제
문제
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
풀이
투 포인터와 누적합을 이용해서 풀었다. 처음에 입력을 받을 때, 각 요소의 값을 저장하는 것이 아니라, 누적합을 배열에 저장한다. 어떤 구간 (i, j) 의 부분합은 i-1 까지의 누적합과 j 까지의 누적합의 차와 같기 때문에 이를 이용해서 투포인터가 가르키고 있는 부분배열의 부분합을 구하고 S 이상인지 확인한다. 만약 S보다 크다면 부분배열의 길이를 현재 저장된 최소 길이와 비교하여 업데이트하고, 부분 배열의 길이가 작으면 작을 수록 좋기 때문에 start의 위치를 값을 증가시킨다. 반대로 S의 값보다 부분합이 작은 경우에는 새로운 숫자를 포함시켜 부분합이 커지게 해야하기 때문에 end 의 값을 증가시킨다.
코드
#include <iostream>
#include <climits>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
int N, S, num;
cin >> N >> S;
int accNums[100001] = { 0, };
for (int i = 1; i <= N; i++) {
cin >> num;
accNums[i] = accNums[i - 1] + num;
}
int start = 1, end = 1;
int minLength = INT_MAX;
while (end <= N) {
if (accNums[end] - accNums[start - 1] >= S) {
minLength = min(minLength, end - start + 1);
++start;
}
else {
++end;
}
}
cout << (minLength == INT_MAX ? 0 : minLength);
}
