[C++][백준 1806] 부분합

문제설명은 더보기를 눌러주세요

문제 링크 :  www.acmicpc.net/problem/1806

문제

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

입력

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

출력

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

예제 입력 

10 15

5 1 3 5 10 7 4 9 2 8

예제 출력 

2

 

-풀이-

투포인터 알고리즘을 사용하는 문제이다.

1. 포인터 두개를 준비하여(st, en), 처음엔 둘다 배열의 처음을 가리키게 한다.

2. st~en까지의 합을 저장할 total변수를 생성한다. (처음 total은 arr[1]로 초기화)

3. while루프를 돌면서, total이 S 이상일 경우 길이(en-st+1)확인 후 최솟값이면 저장

4. total보다 S가 크면, en을 하나 늘려주고 total 변수에 arr[en]을 더한다. 
    (쉽게말해 total을 st~en -> st~en+1로 만드는 것)

5. total보다 S가 작으면, total 변수에 arr[st]를 빼고 st를 하나 늘려준다.
    (쉽게말해 total을 st~en -> st+1~en로 만드는 것)

6. st가 en보다 커지거나, en이 끝에 도달하면 끝.

-코드-

#include<iostream>
#include<algorithm>
using namespace std;
int arr[100001]; 
int N, M; //S대신 M사용
int main(){
    cin >> N >> M;
    for(int i=1; i<=N; i++) cin >> arr[i];
    int st=1, en=1, total = arr[1], ans = 987654321;
    while(st <= en && en <= N){
        if(total >= M) ans = min(ans, (en-st+1));
        if(total < M) {
            en++; 
            total += arr[en];
        } else {
            total -= arr[st];
            st++;
        }
    }
    if(ans == 987654321) cout << "0";
    else cout << ans;
}

 

- 결과 -