[백준/C++] 부분합

1806번: 부분합 (acmicpc.net)

1806번: 부분합

문제유형

*누적 합

문제

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

입출력 예제

 

(입력 1)	10 15 5 1 3 5 10 7 4 9 2 8
(출력 1)	2

풀이

1. N짜리 수열을 저장하는 arr배열과, 누적합을 저장하는 total배열을 만들어 준다.

2. ans변수를 만들어서 N+1로 초기화를 한 뒤, 투 포인터인 start와 end을 이용해 부분합이 S이상이 되는 가장 짧은 구간을 찾는다. 매 짧은 구간을 찾는 경우, ans을 업데이트 해준다.

3. for문을 지나고, ans값이 초기값 N+1과 같다면 부분 배열이 없는 것이므로 0을 출력하게 하고 그 외에는 ans를 출력한다.

코드

 

#include <iostream>

using namespace std;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
    
    int N, S;
    cin >> N >> S;
    
    int arr[N+1], total[N+1];
    for (int i=1; i<=N; i++) {
        cin >> arr[i];
        total[i] = arr[i] + total[i-1];
    }
    
    int ans=N+1;
    for (int start=0, end=1; end<=N; end++) {
        while (total[end] - total[start] >= S) {
            ans = min(ans, end-start);
            start++;
        }
    }

    if (ans==N+1) {
        cout << 0;
    } else {
        cout << ans;
    }
   

	return 0;
}