[C++] 1806번 부분합 - 두 포인터

#include <iostream>

#define LOOP(i, N) for(int i=1; i<=N; i++)

#define MAX_NUM_CNT 100001

using namespace std;
typedef long long int lld;

int N, S;  //숫자의 개수 N, 부분합 S
int num[MAX_NUM_CNT];  //수열
lld sum;  //수열의 합
int min_length;  //가장 짧은 길이

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    min_length=MAX_NUM_CNT;
    
    cin >> N >> S;
    LOOP(i, N) cin >> num[i];
    
    int l, r; l=r=1;  //왼쪽, 오른쪽
    sum=num[1];
    while(l<=r && r<=MAX_NUM_CNT-1) {  //두 포인터
        if(sum>=S) {  //S보다 합이 크면 왼쪽부터 줄이기
            min_length = min_length<r-l+1 ? min_length:r-l+1;
            sum-=num[l];
            l++;
        }
        else {  //S보다 합이 작으면 오른쪽부터 늘리기
            r++;
            sum+=num[r];
        }
    }
    cout << (min_length==MAX_NUM_CNT ? 0:min_length);
    
    return 0;
}

간단했다. 이제 골드 4도 나름 쉬워진 것 같다. 두 포인터도 개념이 간단해서 처음 봐도 금방 이해할 수 있었다.

 

<시행착오>

1. 그러한 합을 만드는 것이 불가능하다면 0을 출력하라. 이거 못읽어서 맨처음에 틀렸다.

 

 

<1806번 반례 모음>

https://bingorithm.tistory.com/13

"백준 1806번-부분합" 반례 모음

 

<투 포인터 알고리즘>

https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0

[Algorithm] Two Pointers, 투 포인터

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.