[투 포인터] BOJ 1806번 부분합 - 오답노트

https://www.acmicpc.net/problem/1806

1806번: 부분합

- 문제파악

N개의 수열이 주어지고 수열의 연속되는 원소의 부분합이 입력으로 주어지는 S이상인 경우 중, 부분합의 길이가 가장 짧은 길이를 출력하라

 

- 정답

투 포인터 연습문제.. 지만 골드 문제다..

 

시작 포인터와 종료 포인터가 있고

시작 포인터는 for문으로 계속 증가 시키고

종료 포인터는 문제의 조건이 성립할 때 멈춘다.

 

해당 문제는 시작 포인터로 부터 연속되는 원소의 부분합이 S 이상일 때 종료 포인터를 멈춘다.

그리고 시작 포인터를 1 증가 시키고 다시 위 행위를 반복한다.

 

이때 종료 포인터 - 시작 포인터 +1 이 가장 작은 수를 출력한다.

 

내가 실수 했던 점은 부분합을 계속 유지하면서 시작포인터가 옮겨 지면 그만큼 값을 빼야하는데, 그렇지 않았다..

 

통과 코드는 아래와 같다.

 

#include "bits/stdc++.h"

using namespace std;

int arr[100005];

int main()
{
    int n, s;
    cin >> n >> s;
  
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    
    int ed = -1;
    int nmin = 0x7fffff;
    long long lsum = 0;
    for (int i = 0; i < n; i++)
    {
        while (ed < n && lsum < s)
        {
            ed++;
            lsum += arr[ed];
        }
        
        if(lsum >= s)
            nmin = min(nmin, ed - i +1);

        lsum -= arr[i];

    }

    if (nmin == 0x7fffff) nmin = 0;

    cout << nmin;

}