백준 1806번 부분합 (C++)

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

1806번: 부분합

이 문제는 투 포인터로 해결이 가능하다.

문제 풀이는 다음과 같다.

 

1. 먼저 배열의 최대길이인 100001을 저장해주고, 초기 부분합의 길이인 1을 저장하자.

int cnt = 1, ans = MAX;

2. 다음은 투 포인터의 위치를 비교하기 위해 설정한 left값과 right값, 그리고 합을 나타내는 sum의 변수이다.

    int left = 0, right = 0;
    sum = v[left];

left와 right모두 0번째부터 시작한다는 것을 기억해두자.

 

3. 다음은 투 포인터를 활용한 while구문이다.

    while(left<=right&&right<n){ // (1)
        if(sum<m){ // (2)
            right++;
            cnt++;
            sum+=v[right];
        }
        else{ // (3)
            if(cnt<ans) ans = cnt;
            sum-=v[left];
            left++;
            cnt--;
            if(left>right&&left<n){ // (4)
                right=left;
                cnt=1;
                sum+=v[right];
            }
        }
    }

먼저 중요한 점은 (1)번에 적힌 조건이다. left가 right보다 커서는 안된며, right이 n 이상이면 안된다.

 

4. 두 번째 구문을 봐보자.

        if(sum<m){ // (2)
            right++;
            cnt++;
            sum+=v[right];
        }

만약 sum이 m보다 작으면 배열의 길이를 늘려줘야 한다는 뜻이다.

때문에 right값을 증가시키고 v[right]을 더해준다. 이때 배열의 길이가 증가했으니 cnt의 값을 +1해주는것도 잊어선 안된다.

 

5. 3번째 구문을 봐보자.

        else{ // (3)
            if(cnt<ans) ans = cnt;
            sum-=v[left];
            left++;
            cnt--;
            if(left>right&&left<n){ // (4)
                right=left;
                cnt=1;
                sum+=v[right];
            }
        }

만약 sum이 m 이상이라면, 이제 배열의 right이 아닌 left를 증가시킬 차례이다.

먼저 부분합의 길이가 ans보다 작으면 ans값을 cnt로 갱신해주자.

이제 left를 증가시켜줘야하는데, 우선 기존에 더해져있던 v[left]의 값을 빼주고 left를 +1해준다. 

이때 감소된 배열의 길이에 따라 cnt의 값을 -1해주는 것을 잊으면 안된다.

 

여기서 중요한건 4번째 구문이다.

예를들어 다음과 같은 상황을 고려해보자.

만약 이런 상황이라면 시작부터 right보다 left가 커서 while문을 빠져나올 수 있다.

때문에 위와 같은 상황을 배제하기 위한 예외조건을 설정해야한다.

 

어차피 v[i]의 값이 m보다 크다면 해당 위치는 left와 right모두 비껴나가야만 한다.

때문에 증가된 left의 위치와 right의 위치를 동일하게하고, 새로 갱신된 right의 위치를 합에 추가해준다.

 

6. 만약 정답의 값이 초기와 동일한 100001이라면 0을 출력해주고, 그렇지 않다면 정답을 그대로 출력해준다.

 

#include <iostream>
#include <vector>
#define MAX 100001
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m, sum = 0, cnt = 1, ans = MAX;
    cin >> n >> m;
    vector<int> v(n);
    for(int i=0; i<n; i++) cin >> v[i];
    int left = 0, right = 0;
    sum = v[left];
    while(left<=right&&right<n){
        if(sum<m){
            right++;
            cnt++;
            sum+=v[right];
        }
        else{
            if(cnt<ans) ans = cnt;
            sum-=v[left];
            left++;
            cnt--;
            if(left>right&&left<n){
                right=left;
                cnt=1;
                sum+=v[right];
            }
        }
    }
    if(ans==MAX) ans = 0;
    cout << ans << "\n";
    return 0;
}

간만에 투 포인터의 개념을 다시 되돌아볼 수 있었던 문제였다.