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

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

1806번: 부분합

문제 풀이

투 포인터를 이용하여 풀이하면 된다.

여기서는 st와 en 두 개의 포인터를 사용한다.

1. 배열 A를 입력받는다.

2. en을 1씩 증가시키면서 total의 값이 S 이상일 경우, 그때 그 값이 최솟값인지 체크를 한다.

만약 en이 N이 되면 배열 끝까지 다 순회한 것이므로 더 이상 체크할 것이 없기 때문에 break 한다.

3. st를 1만큼 증가시키고, 다시 과정을 반복한다.

아래는 위 과정을 구현한 것이다.

다만, 처음에는 total을 따로 st부터 en까지의 값을 모두 더하는 함수로 빼서 구현했다가 시간 초과에 막혔었다.

단순하게 더하고 for문이 끝날 때 빼주면 되는 것이었는데 너무 복잡하게 생각해서 오히려 틀렸다.

#include <iostream>

using namespace std;

int n, s;
int A[100005];
int st, en;
int mn = 0x7fffffff;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> s;
    for(int i = 0; i < n; i++) cin >> A[i];
    int total = A[0];
    for(; st < n; st++){
        while(en < n and total < s){
            en++;
            if(en != n) total += A[en];
        }
        if(en == n) break;
        mn = min(mn, en-st+1);
        total -= A[st];
    }
    if(mn == 0x7fffffff) cout << 0;
    else cout << mn;
}