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

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

1806번: 부분합

투 포인터 알고리즘을 이용하여 O(N)만에 풀 수 있는 문제였다.

이번 문제에서 겪었던 어려운 점은 투 포인터의 반복문을 돌리면서 '어떻게 조건을 분기시키며

그 조건 결과에는 어떤 연산을 시켜야 할까'가 고민이었다.

 

투 포인터라는 이름에 꽂혀서일까 두 개의 조건으로만 분기하려 했었다.

• sum이 s보다 클 때
• sum이 s와 같을 때
• sum이 s보다 작을 때

이 3가지를 따지면 그에 맞는 코드를 구현할 수 있다.

우선 크거나 같을 때의 길이의 최솟값이므로 2개의 조건에서는 항상 길이를 최신화시킨다.

 

[조건 (1)]

if(sum > s){
    result = min(result, r - l + 1);
    sum -= v[l];
    l++;
}

sum이 s보다 클 때는 최소의 길이를 구하기 때문에 left를 움직여준다.

 

[조건 (2)]

else if(sum == s){
    result = min(result, r - l + 1);
    sum += v[++r];
}

sum과 s가 같을 때는 left를 움직이면 sum이 s보다 작아지기 때문에 항상 sum이 s보다 커지기를 그리디하게끔 생각하여 right를 움직인다.

 

[조건 (3)]

else{
    sum += v[++r];
}

sum이 s보다 작은 경우는 right를 옮기며 sum을 더 크게 만든다.

 

투 포인터를 활용하는 법을 더 숙지해야겠다.

 

[AC 코드]

#include <iostream>
#include <vector>
using namespace std;

int n, s;
vector<int> v;
int result = 100000;

void twoPointers(){
    int l = 0, r = 0;
    long sum = v[0];
    
    while(l <= r && r < n){
        if(sum > s){
            result = min(result, r - l + 1);
            sum -= v[l];
            l++;
        }
        else if(sum == s){
            result = min(result, r - l + 1);
            sum += v[++r];
        }
        else{
            sum += v[++r];
        }
        
        
    }
}

int main(){
    cin >> n >> s;
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        v.push_back(a);
    }
    
    twoPointers();
    
    if(result == 100000) cout << 0;
    else cout << result;
    return 0;
}